A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix^†^†thanks: Supported by the ERC Starting Grants ScaleOpt and QIP.

Daniel Dadush Centrum Wiskunde & Informatica, The Netherlands. Sophie Huiberts Centrum Wiskunde & Informatica, The Netherlands. Bento Natura Department of Mathematics, London School of Economics. László A. Végh Department of Mathematics, London School of Economics.

Abstract

Following the breakthrough work of Tardos (Oper. Res. ’86) in the bit-complexity model, Vavasis and Ye (Math. Prog. ’96) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) $max c^{⊤} x, A x = b, x \geq 0, A \in R^{m \times n}$ , Vavasis and Ye developed a primal-dual interior point method using a ‘layered least squares’ (LLS) step, and showed that $O (n^{3.5} log ({¯ χ}_{A} + n))$ iterations suffice to solve (LP) exactly, where ${¯ χ}_{A}$ is a condition measure controlling the size of solutions to linear systems related to $A$ .

Monteiro and Tsuchiya (SIAM J. Optim. ’03), noting that the central path is invariant under rescalings of the columns of $A$ and $c$ , asked whether there exists an LP algorithm depending instead on the measure ${¯ χ}_{A}^{*}$ , defined as the minimum ${¯ χ}_{A D}$ value achievable by a column rescaling $A D$ of $A$ , and gave strong evidence that this should be the case. We resolve this open question affirmatively.

Our first main contribution is an $O (m^{2} n^{2} + n^{3})$ time algorithm which works on the linear matroid of $A$ to compute a nearly optimal diagonal rescaling $D$ satisfying ${¯ χ}_{A D} \leq n ({¯ χ}^{*})^{3}$ . This algorithm also allows us to approximate the value of ${¯ χ}_{A}$ up to a factor $n ({¯ χ}^{*})^{2}$ . This result is in (surprising) contrast to that of Tunçel (Math. Prog. ’99), who showed NP-hardness for approximating ${¯ χ}_{A}$ to within $2^{p o l y (r a n k (A))}$ . The key insight for our algorithm is to work with ratios $g_{i} / g_{j}$ of circuits of $A$ —i.e., minimal linear dependencies $A g = 0$ —which allow us to approximate the value of ${¯ χ}_{A}^{*}$ by a maximum geometric mean cycle computation in what we call the ‘circuit ratio digraph’ of $A$ .

While this resolves Monteiro and Tsuchiya’s question by appropriate preprocessing, it falls short of providing either a truly scaling invariant algorithm or an improvement upon the base LLS analysis. In this vein, as our second main contribution we develop a scaling invariant LLS algorithm, which uses and dynamically maintains improving estimates of the circuit ratio digraph, together with a refined potential function based analysis for LLS algorithms in general. With this analysis, we derive an improved $O (n^{2.5} log n log ({¯ χ}_{A}^{*} + n))$ iteration bound for optimally solving (LP) using our algorithm. The same argument also yields a factor $n / log n$ improvement on the iteration complexity bound of the original Vavasis-Ye algorithm.

\listoftodos

1 Introduction

The linear programming (LP) problem in primal-dual form is to solve

\begin{matrix} min & c^{⊤} x A x & = b x & \geq 0, \end{matrix} \begin{matrix} max & y^{⊤} b A^{⊤} y + s & = c s & \geq 0, \end{matrix}

(LP)

where $A \in R^{m \times n}$ , $r a n k (A) = m \leq n$ , $b \in R^{m}$ , $c \in R^{n}$ are given in the input, and $x, s \in R^{n}$ , $y \in R^{m}$ are the variables. We consider the program in $x$ to be the primal problem and the program in $y, s$ to be the dual problem.

Khachiyan [Kha79] used the ellipsoid method to give the first polynomial time LP algorithm in the bit-complexity model, that is, polynomial in the bit description length of $A, b, c$ . Following Khachiyan’s work, the now forty year old open question is whether there exists a strongly polynomial time algorithm for LP. The task is to solve LP using $p o l y (n, m)$ basic arithmetic operations. Furthermore, the algorithm must be in PSPACE, that is, the numbers occurring in the computations must remain polynomially bounded in the input size. Known strongly polynomially solvable LP problems classes include: feasibility for two variable per inequality systems [Meg83], the minimum-cost circulation problem [Tar85], the maximum generalized flow problem [Vég17, OV17], and discounted Markov decision problems [Ye05, Ye11].

For more general LP classes, for which strongly polynomial algorithms are not known, the principal line of attack has been to reduce the numerical complexity of LP algorithms. More precisely, the goal has been to develop algorithms whose number of arithmetic operations depend on natural condition measures of the base LP; at a high level, these condition measures attempt to finely measure the “intrinsic complexity” of the LP. An important line of work in this area has been to parametrize LPs by the “niceness” of their solutions (e.g. the depth of the most interior point), where relevant examples include the Goffin measure [Gof80] for conic systems and Renegar’s distance to ill-posedness for general LPs [Ren94, Ren95], and bounded ratios between the nonzero entries in basic feasible solutions [Chu14, KM13].

Parametrizing by the constraint matrix

A second line of research, and the main focus of this work, makes no assumptions on the “niceness” of solutions and instead focuses on the complexity of the constraint matrix $A$ . The first breakthrough in this area was given by Tardos [Tar86], who showed that if $A$ has integer entries and all square submatrices of $A$ have determinant at most $Δ$ in absolute value, then (LP) can be solved in time poly $(n, m, log Δ)$ . This is achieved by finding the exact solutions to $n^{2}$ rounded LPs derived from the original LP, with the right hand side vector and cost function being integers of absolute value bounded in terms of $n$ and $Δ$ . From $n$ such rounded problem instances, one can infer, via proximity results, that a constraint $x_{i} = 0$ must be valid for every optimal solution. The process continues by induction until the optimal primal face is identified.

Path-following methods and the Vavasis-Ye algorithm

In a seminal work, Vavasis and Ye [VY96] introduced a new type of interior-point method that optimally solves (LP) within $O (n^{3.5} log ({¯ χ}_{A} + n))$ iterations, where the condition number ${¯ χ}_{A}$ controls the size of solutions to certain linear systems related to the kernel of $A$ (see Section 2 for the formal definition).

Before detailing the Vavasis-Ye (henceforth VY) algorithm, we recall the basics of path following interior-point methods. If both the primal and dual problems in (LP) are strictly feasible, the central path for (LP) is the curve $((x (μ), y (μ), s (μ)) : μ > 0)$ defined by

$x (μ)_{i} s (μ)_{i}$	$= μ, \forall i \in [n]$	(CP)
$A x (μ)$	$= b, x (μ) > 0,$
$A^{⊤} y (μ) + s (μ)$	$= c, s (μ) > 0,$

which converges to complementary optimal primal and dual solutions $(x^{*}, y^{*}, s^{*})$ as $μ \to 0$ , recalling that the optimality gap at time $μ$ is exactly $x (μ)^{⊤} s (μ) = n μ$ . We thus refer to $μ$ as the normalized dualized gap. Methods that “follow the path” generate iterates that stay in a certain neighborhood around it while trying to achieve rapid multiplicative progress w.r.t. to $μ$ , where given $(x, y, s)$ close to the path, we define the effective $μ$ as $μ (x, y, s) = \sum_{i = 1}^{n} x_{i} s_{i} / n$ . In general, the direction of movement at each iteration is computed by solving a carefully chosen linear system. Given a target parameter $μ^{'}$ and starting point close to the path at parameter $μ$ , standard path following methods [Gon92] can compute a point at parameter below $μ^{'}$ in at most $O (\sqrt{n} log (μ / μ^{'}))$ iterations, and hence the quantity $log (μ / μ^{'})$ can be usefully interpreted as the length of the corresponding segment of the central path.

Crossover events and layered least squares steps

At a very high level, Vavasis and Ye show that the central path can be decomposed into at most $(\frac{n}{2})$ short but curved segments, possibly joined by long (apriori unbounded) but very straight segments. At the end of each curved segment, they show that a new ordering relation $x_{i} (μ) > x_{j} (μ)$ —called a ‘crossover event’—is implicitly learned, where this relation did not hold at the start of the segment, but will hold at every point from the end of the segment onwards. These $(\frac{n}{2})$ relations give a combinatorial way to measure progress along the central path. In contrast to Tardos’s algorithm, where the main progress is setting variables to zero explicitly, the variables participating in crossover events cannot be identified, only their existence is shown.

At a technical level, the VY algorithm is a variant of the Mizuno-Todd-Ye [MTY93] predictor-corrector method (MTY P-C). In predictor-corrector methods, corrector steps bring an iterate closer to the path, i.e., improve centrality, and predictor steps “shoot down” the path, i.e., reduce $μ$ without losing too much centrality. VY’s main algorithmic innovation was the introduction of a new predictor step, called the ‘layered least squares’ (LLS) step, which crucially allowed them to cross each aforementioned “straight” segment of the central path in a single step, recalling that these straight segments may be arbitrarily long. To traverse the short and curved segments of the path, the standard predictor step, known as affine scaling (AS), in fact suffices.

To compute the LLS direction, the variables are decomposed into ‘layers’ $J_{1} \cup J_{2} \cup \dots \cup J_{p} = [n]$ . The goal of such a decomposition is to eventually learn a refinement of the optimal partition of the variables $B^{*} \cup N^{*} = [n]$ , where $B^{*} := {i \in [n] : x_{i}^{*} > 0}$ and $N^{*} := {i \in [n] : s_{i}^{*} > 0}$ for the limit optimal solution $(x^{*}, y^{*}, s^{*})$ .

The primal affine scaling direction can be equivalently described by solving a weighted least squares problem in $Ker (A)$ , with respect to a weighting defined according to the current iterate. The primal LLS direction is obtained by solving a series of weighted least squares problems, starting with focusing only on the final layer $J_{p}$ . This solution is gradually extended to the higher layers (which refers to layers with lower indices). The dual directions have analogous interpretations, with the solutions on the layers obtained in the opposite direction, starting with $J_{1}$ . If we use the two-level layering $J_{1} = B^{*}$ , $J_{2} = N^{*}$ , and are sufficiently close to the limit $(x^{*}, y^{*}, s^{*})$ of the central path, then the LLS step reaches an exact optimal solution in a single step. We note that standard AS steps generically never find an exact optimal solution, and thus some form of “LLS rounding” is always necessary to achieve finite termination.

Of course, guessing $B^{*}$ and $N^{*}$ correctly is just as hard as solving (LP). Still, if we work with a “good” layering, these will reveal new information about the “optimal order” of the variables, where $B^{*}$ is placed on higher layers than $N^{*}$ . The crossover events correspond to swapping two wrongly ordered variables into the correct ordering. Namely, a variable $i \in B^{*}$ and $j \in N^{*}$ are currently ordered on the same layer, or $j$ is in a higher layer than $i$ . After the crossover event, $i$ will always be placed on a higher layer than $j$ .

Computing good layerings and the ${¯ χ}_{A}$ condition measure

Given the above discussion, the obvious question is how to come up with “good” layerings? The philosophy behind LLS can be stated as saying that if modifying a set of variables $x_{I}$ barely affects the variables in $x_{[n] ∖ I}$ (recalling that movement is constrained to $Δ x \in Ker (A)$ ), then one should optimize over $x_{I}$ without regard to the effect on $x_{[n] ∖ I}$ ; hence $x_{I}$ should be placed on lower layers.

VY’s strategy for computing such layerings was to directly use the size of the coordinates of the current iterate $x$ (where $(x, y, s)$ is a point near the central path). In particular, assuming $x_{1} \geq x_{2} \geq \dots \geq x_{n}$ , the layering $J_{1} \cup J_{2} \cup \dots \cup J_{p} = [n]$ corresponds to consecutive intervals constructed in decreasing order of $x_{i}$ values. The break between $J_{i}$ and $J_{i + 1}$ occurs if the gap $x_{r} / x_{r + 1} > g$ , where $r$ is the rightmost element of $J_{i}$ and $g > 0$ is a threshold parameter. Thus, the expectation is that if $x_{i} > g x_{j}$ , then a small multiplicative change to $x_{j}$ , subject to moving in $Ker (A)$ , should induce a small multiplicative change to $x_{i}$ . By proximity to the central path, the dual ordering is reversed as mentioned above.

The threshold $g$ for which this was justified in VY was a function of the ${¯ χ}_{A}$ condition measure. We now provide a convenient definition, which immediately yields this justification (see Proposition 2.4). Letting $W = Ker (A)$ and $π_{I} (W) = {x_{I} : x \in W}$ , we define ${¯ χ}_{A} := {¯ χ}_{W}$ as the minimum number $M \geq 1$ such that for any $\emptyset \neq I \subseteq [n]$ and $z \in π_{I} (W)$ , there exists $y \in W$ with $y_{I} = z$ and $∥ y ∥ \leq M ∥ z ∥$ . Thus, a change of $ε$ in variables in $I$ can be lifted to a change of at most ${¯ χ}_{A} ε$ in variables in $[n] ∖ I$ . Crucially, $¯ χ$ is a “self-dual” quantity. That is, ${¯ χ}_{W} = {¯ χ}_{W^{⊥}}$ , where $W^{⊥} = r a n g e (A^{⊤})$ is the movement subspace for the dual problem, justifying the reversed layering for the dual (see Sections 2 for more details).

The question of scale invariance and ${¯ χ}_{A}^{*}$

While the VY layering procedure is powerful, its properties are somewhat mismatched with those of the central path. In particular, variable ordering information has no intrinsic meaning on the central path, as the path itself is scaling invariant. Namely the central path point $(x (μ), y (μ), s (μ))$ w.r.t. the problem instance $(A, b, c)$ is in bijective correspondence with the central path point $(D^{- 1} x (μ), D y (μ), D s (μ)))$ w.r.t. the problem instance $(A D, D c, b)$ for any positive definite diagonal matrix $D$ . The standard path following algorithms are also scaling invariant in this sense.

This lead Monteiro and Tsuchiya [MT03] to ask whether a scaling invariant LLS algorithm exists. They noted that any such algorithm would then depend on the potentially much smaller parameter

{¯ χ}_{A}^{*} := inf {{¯ χ}_{A D} : D ≻ 0 diagonal % positive definite},

(1)

where the infimum is taken over the set of $n \times n$ positive diagonal matrices. Thus, Monteiro and Tsuchiya’s question can be rephrased as to whether there exists an exact LP algorithm with running time poly $(n, m, log {¯ χ}_{A}^{*})$ .

Substantial progress on this question was made in the followup works [MT05, LMT09]. [MT05] showed that the number of iterations of the MTY predictor-corrector algorithm [MTY93] can get from $μ_{0} > 0$ to $η > 0$ on the central path in $O (n^{3.5} log {¯ χ}^{*} + min {n^{2} log log (μ^{0} / η), log (μ^{0} / η)})$ iterations. This is attained by showing that the standard AS steps are reasonably close to the LLS steps. This proximity can be used to show that the AS steps can traverse the curved parts of the central path in the same iteration complexity bound as the VY algorithm. Moreover, on the “straight” parts of the path, the rate of progress amplifies geometrically, thus attaining a $log log$ convergence on these parts. Subsequently [LMT09] developed an affine invariant trust region step, which traverses the full path in $O (n^{3.5} log ({¯ χ}_{A}^{*} + n))$ iterations. However, each iteration is weakly polynomial in $b$ and $c$ . The question of developing an LP algorithm with complexity bound poly $(n, m, log {¯ χ}_{A}^{*})$ thus remained open.

A related open problem to the above is whether it is possible to compute a near-optimal rescaling $D$ for program (1)? This would give an alternate pathway to the desired LP algorithm by simply preprocessing the matrix $A$ . The related question of approximating ${¯ χ}_{A}$ was already studied by Tunçel [Tun99], who showed NP-hardness for approximating ${¯ χ}_{A}$ to within a $2^{p o l y (r a n k (A))}$ factor. Taken at face value, this may seem to suggest that approximating the rescaling $D$ should be hard.

A further open question is whether Vavasis and Ye’s base cross-over analysis can be improved. Ye in [Ye06] showed that the iteration complexity can be reduced to $O (n^{2.5} log ({¯ χ}_{A} + n))$ for feasibility problems and further to $O (n^{1.5} log ({¯ χ}_{A} + n))$ for homogeneous systems, though the $O (n^{3.5} log ({¯ χ}_{A} + n))$ bound for optimization has remained unimproved since [VY96].

Our contributions.

In this work, we resolve all of the above questions in the affirmative. We detail our contributions below.

1. Finding an approximately optimal rescaling. As our first contribution, we give an $O (m^{2} n^{2} + n^{3})$ time algorithm which works on the linear matroid of $A$ to compute a diagonal rescaling matrix $D$ which achieves ${¯ χ}_{A D} \leq n ({¯ χ}_{A}^{*})^{3}$ , given any $m \times n$ matrix $A$ . Furthermore, this same algorithm allows us to approximate ${¯ χ}_{A}$ to within a factor $n ({¯ χ}_{A}^{*})^{2}$ . The algorithm bypasses Tunçel’s hardness result by allowing the approximation factor to depend on $A$ itself, namely on ${¯ χ}_{A}^{*}$ . This gives a simple first answer to Monteiro and Tsuchiya’s question: by applying the Vavasis-Ye algorithm directly on the preprocessed $A$ matrix, we may solve any LP with constraint matrix $A$ using $O (n^{3.5} (log {¯ χ}_{A}^{*} + n))$ iterations. Note that the approximation factor $n ({¯ χ}_{A}^{*})^{2}$ increases the runtime only by a constant factor.

To achieve this result, we work directly with the circuits of $A$ , where a circuit $C \subseteq [n]$ is $C = s u p p (g)$ for a minimal linear dependency $A g = 0$ . With each circuit, we can associate a vector $g^{C} \in Ker (A)$ with $s u p p (g^{C}) = C$ that is unique up to scaling. By the ‘circuit ratio’ of $(i, j)$ , we mean the largest ratio $| g_{j}^{C} / g_{i}^{C} |$ taken over every circuit $C$ of $A$ such that $i, j \in C$ . As our first observation, we show that the maximum of all circuit ratios, which we call the ‘circuit imbalance measure’, in fact characterizes ${¯ χ}_{A}$ up to a factor $n$ . This measure was first studied by Vavasis [Vav94], who showed that it lower bounds ${¯ χ}_{A}$ , though, as far as we are aware, our upper bound is new. The circuit ratios of each pair $(i, j)$ induces a weighted directed graph we call the circuit ratio digraph of $A$ . From here, our main result is that ${¯ χ}_{A}^{*}$ is up to a factor $n$ equal to the maximum geometric mean cycle in the circuit ratio digraph. Our approximation algorithm populates the circuit ratio digraph with ratios for each $i, j$ using basic matroid techniques, and then computes a rescaling by solving the dual of the maximum geometric mean ratio cycle on the ‘approximate circuit ratio digraph’.

2. Scaling invariant LLS algorithm. While the above yields an LP algorithm with poly $(n, m, log {¯ χ}_{A}^{*})$ running time, it does not satisfactorily address Monteiro and Tsuchiya’s question for a scaling invariant algorithm. As our second contribution, we use the circuit ratio digraph directly to give a natural scaling invariant LLS layering algorithm together with a scaling invariant crossover analysis.

At a conceptual level, we show that the circuit ratios give a scale invariant way to measure whether ‘ $x_{i} > x_{j}$ ’ and enable a natural layering algorithm. Let $κ_{i j}$ be the circuit imbalance between $i$ and $j$ , i.e., the maximum value $| g_{j} / g_{i} |$ for a minimal kernel solution $g$ containing $i$ and $j$ in the support. Given the circuit ratio graph induced by $κ$ and a primal point $x$ near the path, our layering algorithm can be described as follows. We first rescale the variables so that $x$ becomes the all ones vector, which rescales $κ_{i j}$ to $κ_{i j} x_{i} / x_{j}$ . We then restrict the graph its edges of length $\geq 1 / p o l y (n)$ —the long edges of the (rescaled) circuit ratio graph—and let the layering $J_{1} \cup J_{2} \cup \dots \cup J_{p}$ be a topological ordering of its strongly connected components (SCC) with edges going from left to right. Intuitively, variables that “affect each other” should be in the same layer, which motivates the SCC definition. It is not hard to see that VY’s original layering algorithm can achieved in this way by artificially declaring the rescaled circuit ratios to be $p o l y (n) {¯ χ}_{A} \cdot x_{i} / x_{j}$ , $\forall (i, j)$ .

We note that our layering algorithm does not in fact have access to the true circuit ratios $κ_{i j}$ , as these are NP-hard to compute. Getting a good enough initial estimate for our purposes however is easy: we let ${^κ}_{i j}$ be the ratio corresponding to an arbitrary circuit containing $i$ and $j$ . This already turns out to be within a factor $({¯ χ}_{A}^{*})^{2}$ from the true value $κ_{i j}$ , which we recall is the maximum over all such circuits. Our layering algorithm in fact learns better circuit ratio estimates if the “lifting costs” of our SCC layering, i.e., how much it costs to lift changes from lower layer variables to higher layers (as in the definition of ${¯ χ}_{A}$ ), are larger than we expected them to be.

For our analysis, we define cross-overs in a scaling invariant way as follows. Before the crossover event, $p o l y (n) ({¯ χ}_{A}^{*})^{n} > κ_{i j} x_{i} / x_{j}$ , and after the crossover event, $p o l y (n) ({¯ χ}_{A}^{*})^{n} < κ_{i j} x_{i} / x_{j}$ for all further central path points. Our analysis relies on ${¯ χ}_{A}^{*}$ in only a minimalistic way, and does not require an estimate on the value of ${¯ χ}_{A}^{*}$ . Namely, it is only used to show that if $i, j \in J_{q}$ , fo a layer $q \in [p]$ , then the rescaled circuit ratio $κ_{i j} x_{i} / x_{j}$ is in the range $(p o l y (n) {¯ χ}_{A}^{*})^{O (\pm | J_{q} |)}$ . The argument to show this crucially utilizes the maximum geometric mean cycle characterization. Furthermore, unlike prior analyses [VY96, MT03], our definition of a “good” layering (i.e., ‘balanced’ layerings, see Section 3.4), is completely independent of ${¯ χ}_{A}^{*}$ .

3. Improved potential analysis. As our third contribution, we improve the Vavasis-Ye crossover analysis using a new and simple potential function based approach. When applied to our new LLS algorithm, we derive an $O (n^{2.5} log n log ({¯ χ}_{A}^{*} + n))$ iteration bound for path following, improving the polynomial term by an $Ω (n / log n)$ factor compared to the VY analysis.

Our potential function can be seen as a fine-grained version of the crossover events as described above. In case of such a crossover event, it is guaranteed that in every subsequent iteration, $i$ is in a layer before $j$ . Instead, we analyze less radical changes: an “event” parametrized by $τ$ means that $i$ and $j$ are currently together on a layer of size $\leq τ$ , and after the event, $i$ is on a layer before $j$ , or if they are together on the same layer, then this layer must have size $\geq 2 τ$ . For every LLS step, we can find a parameter $τ$ such that an event of this type happens concurrently for at least $τ - 1$ pairs within the next $O (\sqrt{n} τ log ({¯ χ}_{A}^{*} + n))$ iterations,

Our improved analysis is also applicable to the original VY algorithm. Let us now comment on the relation between the VY algorithm and our new algorithm. The VY algorithm starts a new layer once $x_{π (i)} > g x_{π (i + 1)}$ between two consecutive variables where the permutation $π$ is a non-increasing order of the $x_{i}$ variables. Here, $g = p o l y (n) ¯ χ$ . Setting the initial ‘estimates’ ${^κ}_{i j} = g / p o l y (n)$ for a suitable polynomial, our algorithm runs the same way as the VY algorithm. Using these estimates, the layering procedure becomes much simpler: there is no need to verify ‘balancedness’ as in our general algorithm.

However, setting $g = {^κ}_{i j}$ has drawbacks. Most importantly, it does not give a lower bound on the true circuit ratio $κ_{i j}$ —to the contrary, $g$ will be an upper bound! In effect, this causes VY’s layers to be “much larger” than ours, and for this reason, the connection to ${¯ χ}^{*}$ is lost. Nevertheless, our potential function analysis can still be adapted to the VY algorithm to obtain the same $Ω (n / log n)$ improvement on the iteration complexity bound; see Section 4.1 for more details.

1.1 Related work

Since the seminal works of Karmarkar [Kar84] and Renegar [Ren88], there has been a tremendous amount of work on speeding up and improving interior-point methods. In contrast to the present work, the focus of these works has mostly been to improve complexity of approximately solving LPs. Progress has taken many forms, such as the development of novel barrier methods, such Vaidya’s volumetric barrier [Vai89] and the recent entropic barrier of Bubeck and Eldan [BE14] and the weighted log-barrier of Lee and Sidford [LS14, LS19], together with new path following techniques, such as the predictor-corrector framework [Meh92, MTY93], as well as advances in fast linear system solving [ST04, LS15]. For this last line, there has been substantial progress in improving IPM by amortizing the cost of the iterative updates, and working with approximate computations, see e.g. [Ren88, Vai89, CLS19, vdB20]. Very recently, Cohen, Lee and Song [CLS19] developed a new inverse maintenance scheme to get a randomized $~ O (n^{2.37} log (1 / ε))$ -time algorithm for $ε$ -approximate LP, which was derandomized by van den Brand [vdB20]. For special classes of LP such as network flow problems, fast algorithms have been obtained by using fast Laplacian solvers, see e.g. [DS08, Mad13]. Given the progress above, we believe it to be an interesting problem to understand to what extent these new numerical techniques can be applied to speed up LLS computations, though we expect that such computations will require very high precision. We note that no attempt has been made in the present work to optimize the complexity of the linear algebra.

Ho and Tunçel [HT02] showed how to extend Tardos’ framework to the real model of computation (i.e., to non-integral $A$ ), providing a blackbox alternative to the VY algorithm. The numerical complexity of the LPs arising in their reduction is controlled by the minimum and maximum subdeterminant of $A$ restricted to non-singular submatrices and the minimum non-zero slack of any basic primal or dual solution over a certain grid of right hand sides and objectives.

With regard to LLS algorithms, the original VY algorithm required explicit knowledge of ${¯ χ}_{A}$ to implement their layering algorithm. [MMT98] showed that this could be avoided by computing all LLS steps associated with $n$ candidate partitions and picking the best one. In particular, they showed that all such LLS steps can be computed in $O (m^{2} n)$ time. [MT03] gave an alternate approach which computes a LLS partition directly from the coefficients of the AS step. We note that these methods crucially rely on the variable ordering, and hence are not scaling invariant. Kitahara and Tsuchiya [KT13], gave a 2-layer LLS step which achieves a running time depending only on ${¯ χ}_{A}^{*}$ and right-hand side $b$ , but with no dependence on the objective, assuming the primal feasible region is bounded.

A series of papers have studied the central path from a differential geometry perspective. Monteiro and Tsuchiya [MT08] showed that a curvature integral of the central path, first introduced by Sonnevend, Stoer, and Zhao [SSZ91], is in fact upper bounded by $O (n^{3.5} log ({¯ χ}_{A}^{*} + n))$ . This has been extended to SDP and symmetric cone programming [KOT14], and also studied in the context of information geometry [KOT13].

Circuits have appeared in several papers on linear and integer optimization (see [DLKS19] and its references). The idea of using circuits within the context of LP algorithms also appears in [DLHL15]. They develop an augmentation framework for LP (as well ILP) and show that a simplex-like algorithm which takes steps according to the “best circuit” direction achieves linear convergence, though these steps are hard to compute.

Our algorithm makes progress towards strongly polynomial solvability of LP, by improving the dependence poly $(n, m, log ¯ χ)$ to poly $(n, m, log {¯ χ}^{*})$ . However, in a remarkable recent paper, Allamigeon et al. [ABGJ18] have shown, using tools from tropical geometry, that path-following methods for the standard logarithmic barrier cannot be strongly polynomial. In particular, they give a parametrized family of instances, where, for sufficiently large parameter values, any sequence of iterations following the central path must be of exponential length—thus, ${¯ χ}^{*}$ will be doubly exponential. We note that it is unclear whether their instance is robust to changing the barrier method itself; e.g., the weighted log-barrier [LS14].

1.2 Organization

Section 2 begins with the necessary background on the condition measures ${¯ χ}_{A}$ and ${¯ χ}_{A}^{*}$ . It culminates in the approximate ${¯ χ}_{A}^{*}$ rescaling and ${¯ χ}_{A}$ approximation algorithm in Section 2.4. This algorithm relies upon the circuit imbalance measure in Section 2.1, the min-max characterization in Section 2.2, and a circuit finding algorithm in Section 2.3.

In Section 3, we develop our scaling invariant interior-point method. Interior-point preliminaries are given in Section 3.1, the layered least squares step is explained in Section 3.3, our scaling invariant layering algorithm is given in Section 3.4, and lastly, our overall algorithm is given in Section 3.5.

In Section 4, we give the potential function proof for the improved iteration bound, relying on technical lemmas. The full proof of these lemmas is deferred to Section 6; however, Section 4 provides the high-level ideas to each proof. Section 4.1 shows that our argument also leads to a factor $Ω (n / log n)$ improvement in the iteration complexity bound of the VY algorithm.

In Section 5, we prove the technical properties of our LLS step, including its proximity to AS and step length estimates. Finally, in Section 7, we discuss the initialization of our interior-point method.

2 Finding an approximately optimal rescaling

Notation

Our notation will largely follow [MT03, MT05]. We let $R_{+ +}$ denote the set of positive reals, and $R_{+}$ the set of nonnegative reals. For $n \in N$ , we let $[n] = {1, 2, \dots, n}$ . Let $e^{i} \in R^{n}$ denote the $i$ th unit vector, and $e \in R^{n}$ the all 1s vector. For a vector $x \in R^{n}$ , we let $Diag (x) \in R^{n \times n}$ denote the diagonal matrix with $x$ on the diagonal. We let $D$ denote the set of all positive definite $n \times n$ diagonal matrices. For $x, y \in R^{n}$ , we use the notation $x y \in R^{n}$ to denote $x y = Diag (x) y = (x_{i} y_{i})_{i \in [n]}$ . The scalar product of the two vectors is denoted as $x^{⊤} y$ . For $p \in Q$ , we also use the notation $x^{p}$ to denote the vector $(x_{i}^{p})_{i \in [n]}$ . Similarly, for $x, y \in R^{n}$ , we let $x / y$ denote the vector $(x_{i} / y_{i})_{i \in [n]}$ . We denote the support of a vector $x \in R^{n}$ by $s u p p (x) = {i \in [n] : x_{i} \neq 0}$ .

For an index subset $I \subseteq [n]$ , we use $π_{I} : R^{n} \to R^{I}$ for the coordinate projection. That is, $π_{I} (x) = x_{I}$ , and for a subset $S \subseteq R^{n}$ , $π_{I} (S) = {x_{I} : x \in S}$ . We let $R_{I}^{n} = {x \in R^{n} : x_{[n] ∖ I} = 0}$ .

For a matrix $B \in R^{n \times k}$ , $I \subset [n]$ and $J \subset [k]$ we let $B_{I, J}$ denote the submatrix of $B$ restricted to the set of rows in $I$ and columns in $J$ . We also use $BI,\vbox\scalebox{.5}{∙}=BI,[k]$ and $BJ=B\vbox\scalebox{.5}{∙},J=B[n],J$ . We let $B^{†} \in R^{k \times n}$ denote the pseudo-inverse of $B$ .

We let $Ker (A)$ denote the kernel of the matrix $A \subseteq R^{m \times n}$ . Throughout, we assume that the matrix $A$ in (LP) has full row rank, and that $n \geq 3$ .

Subspace formulation

Throughout the paper, we let $W = Ker (A) \subseteq R^{n}$ denote the kernel of the matrix $A$ . Using this notation, (LP) can be written in the form

\begin{matrix} min & c^{⊤} x x & \in W + d x & \geq 0, \end{matrix} \begin{matrix} max & d^{⊤} (c - s) s & \in W^{⊥} + c s & \geq 0, \end{matrix}

(2)

where $d \in R^{n}$ satisfies $A d = b$ .

The condition number $¯ χ$

The condition number ${¯ χ}_{A}$ is defined as

	${¯ χ}_{A}$	$= sup {∥ A^{⊤} {(A D A^{⊤})}^{- 1} A D ∥ : D \in D}$		(3)
				(3)

This condition number was first studied by Dikin [Dik67], Stewart [Ste89], and Todd [Tod90], among others, and plays a key role in the analysis of the Vavasis-Ye interior point method [VY96]. There is an extensive literature on the properties and applications of ${¯ χ}_{A}$ , as well as its relations to other condition numbers. We refer the reader to the papers [HT02, MT03, VY96] for further results and references.

It is important to note that ${¯ χ}_{A}$ only depends on the subspace $W = Ker (A)$ . Hence, we can also write ${¯ χ}_{W}$ for a subspace $W \subseteq R^{n}$ , defined to be equal to ${¯ χ}_{A}$ for some matrix $A \in R^{k \times n}$ with $W = Ker (A)$ . We will use the notations ${¯ χ}_{A}$ and ${¯ χ}_{W}$ interchangeably.

The next lemma summarizes some important known properties of ${¯ χ}_{A}$ .

Proposition 2.1.

Let $A \in R^{m \times n}$ with full row rank and $W = Ker (A)$ .

If the entries of $A$ are all integers, then ${¯ χ}_{A}$ is bounded by $2^{O (L_{A})}$ , where $L_{A}$ is the input bit length of $A$ .
${¯ χ}_{A} = max {∥ B^{- 1} A ∥ : B non-singular m \times m -submatrix of% A}$ .
Let the columns of $B \in R^{n \times (n - m)}$ form an orthonormal basis of $W$ . Then

$¯χW=max{∥BB†I,\vbox\scalebox{.5}{∙% }∥:∅≠I⊂[n]}.$
${¯ χ}_{W} = {¯ χ}_{W^{⊥}}$ .

Proof.

Part a was proved in [VY96, Lemma 24]. For part b, see [TTY01, Theorem 1] and [VY96, Lemma 3]. In part c, the direction $\geq$ was proved in [Ste89], and the direction $\leq$ in [O’L90]. The duality statement d was shown in [GL97]. ∎

In Proposition 3.8, we will also give another proof of d. We now define the lifting map, a key operation in this paper, and explain its connection to ${¯ χ}_{A}$ .

Definition 2.2.

Let us define the lifting map $L_{I}^{W} : π_{I} (W) \to W$ by

L_{I}^{W} (p) = a r g m i n {∥ z ∥ : z_{I} = p, z \in W} .

Note that $L_{I}^{W}$ is the unique linear map from $π_{I} (W)$ to $W$ such that $L_{I}^{W} (p)_{I} = p$ and $L_{I}^{W} (p)$ is orthogonal to $W \cap R_{[n] ∖ I}^{n}$ .

Lemma 2.3.

Let $W \subseteq R^{n}$ be an $(n - m)$ -dimensional linear subspace. Let the columns of $B \in R^{n \times (n - m)}$ denote an orthonormal basis of $W$ . Then, viewing $L_{I}^{W}$ as a matrix,

LWI=BB†I,\vbox\scalebox{.5}{∙}.

Proof.

If $p \in π_{I} (W)$ , then $p=BI,\vbox\scalebox{.5}{∙}y$ for some $y \in R^{n - m}$ . By the well-known property of the pseudo-inverse, $B†I,\vbox\scalebox{.5}{∙}p=argminp=BI,\vbox\scalebox{.5}{∙}% y∥y∥$ . This solution satisfies $πI(BB†I,\vbox\scalebox{.5}{∙}p)=p$ , $BB†I,\vbox\scalebox{.5}{∙}p∈W$ . Since the columns of $B$ form form an orthonormal basis of $W$ , we have that $∥BB†I,\vbox\scalebox{.5}{∙}p∥=∥B†I,\vbox\scalebox{.5}{∙}p∥$ . Consequently, $BB†I,\vbox\scalebox{.5}{∙}p$ is the minimum-norm point with the above properties. ∎

The above lemma and Proposition 2.1 c yield the following characterization. This will be the most suitable characterization of ${¯ χ}_{W}$ for our purposes.

Proposition 2.4.

For a linear subspace $W \subseteq R^{n}$ ,

The following notation will be convenient for our algorithm. For a subspace $W \subseteq R^{n}$ and an index set $I \subseteq [n]$ , if $π_{I} (W) \neq {0}$ , we define the lifting score

ℓ^{W} (I) := \sqrt{∥ L_{I}^{W} ∥^{2} - 1} .

(4)

Otherwise, we define $ℓ^{W} (I) = 0$ . This means that for any $z \in π_{I} (W)$ and $x = L_{I}^{W} (z)$ , $∥ x_{[n] ∖ I} ∥ \leq ℓ^{W} (I) ∥ z ∥$ .

The condition number ${¯ χ}_{A}^{*}$

For every $D \in D$ , we can consider the condition number ${¯ χ}_{W D} = {¯ χ}_{A D^{- 1}}$ . We let

{¯ χ}_{W}^{*} = {¯ χ}_{A}^{*} = inf {{¯ χ}_{W D} : D \in D}

denote the best possible value of $¯ χ$ that can be attained by rescaling the coordinates of $W$ . The main result of this section is the following theorem.

Theorem 2.5.

There is an $O (n^{2} m^{2} + n^{3})$ time algorithm that for any matrix $A \in R^{m \times n}$ computes a $t$ such that

t \leq {¯ χ}_{W} \leq t n ({¯ χ}_{W}^{*})^{2}

and a $D \in D$ such that

{¯ χ}_{W}^{*} \leq {¯ χ}_{W D} \leq n ({¯ χ}_{W}^{*})^{3} .

2.1 The circuit imbalance measure

We next introduce the circuit imbalance measure, a more combinatorial condition number, and show that it gives a good proxy to ${¯ χ}_{A}$ .

Definition 2.6.

For a linear subspace $W \subseteq R^{n}$ and a matrix $A$ such that $W = Ker (A)$ , a circuit is an inclusion-wise minimal dependent set of columns of $A$ . Equivalently, a circuit is a set $C \subseteq [n]$ such that $W \cap R_{C}^{n}$ is one-dimensional and that no strict subset of $C$ has this property. Any circuit is associated with a vector $g \in W$ with inclusion-wise minimal support. The set of circuits of $W$ is denoted $C_{W}$ .

Note that these are also known as the circuits in the linear matroid associated with $A$ .

Definition 2.7.

For a circuit $C \in C_{W}$ , let $g^{C} \in W$ be such that $s u p p (g^{C}) = C$ . For $i, j \in C$ , we let

κ_{i j}^{W} (C) = \frac{g_{j}^{C}}{g_{i}^{C}} .

(5)

For any $i, j \in [n]$ , we define the circuit ratio as the maximum of $κ_{i j}^{W} (C)$ over all choices of the circuit $C$ :

κ_{i j}^{W} = max {κ_{i j}^{W} (C) : C \in C_{W}, i, j \in C} .

(6)

By convention we set $κ_{i j}^{W} = 0$ if there is no circuit supporting $i$ and $j$ . Further, we define the circuit imbalance measure as

κ_{W} = max {κ_{i j}^{W} : i, j \in [n]} .

Minimizing over all coordinate rescalings, we define

κ_{W}^{*} = min {κ_{W D} : D \in D} .

We omit the index $W$ whenever it is clear from context. In such cases, for $D = Diag (d) \in D$ , we write $κ_{i j}^{d} = κ_{i j}^{W D}$ and $κ^{d} = κ_{W}^{d} = κ_{W D}$ .

We want to remark that a priori it is not clear that $κ_{W}^{*}$ is well-defined. Theorem 2.13 will show that the minimum of ${κ_{W D} : D \in D}$ is indeed attained. Observe that $κ_{i j}^{W} (C)$ does not depend on the choice of $g$ , since there is only a single choice up to scalar multiplication.

The circuit ratio, as well as the circuit imbalance measure, are self-dual.

Lemma 2.8.

For any subspace $W \subseteq R^{n}$ and $i, j \in [n]$ , $κ_{i j}^{W} = κ_{j i}^{W^{⊥}}$ .

Proof.

Let $C \in C_{W}$ and $g^{C} \in W \cap R_{C}^{n}$ be its corresponding vector such that $κ_{i j} = κ_{i j} (C) = | g_{j} / g_{i} |$ . We construct a circuit solution in $W^{⊥}$ that certifies $κ_{i j}^{W} \geq κ_{j i}^{W^{⊥}}$ .

Define $h \in R^{C}$ by $h_{i} = g_{j}, h_{j} = - g_{i}$ and $h_{k} = 0$ for all $k \in C ∖ {i, j}$ . Then, $h$ is orthogonal to $g$ by construction, and hence we have $h \in π_{C} (W \cap R_{C}^{n})^{⊥} = π_{C} (W^{⊥})$ .

We will lift the vector $h$ to a circuit solution in $W^{⊥}$ . The next procedure will be applied first for $I = C$ , and extended one coordinate at a time; we terminate once $I = [n]$ . Suppose we have any set $I \subset [n]$ and vector $v \in π_{I} (W^{⊥})$ , such that $v$ is a circuit solution $s u p p (v) \in C_{π_{I} (W^{⊥})}$ . For the starting $I = C$ , the vector $v = h$ is a suitable choice. Pick an arbitrary $i \in [n] ∖ I$ . We look for a circuit solution $v^{'} \in π_{I \cup {i}} (W^{⊥})$ with $v_{I}^{'} = v$ . Let $V = π_{I \cup {i}} (W^{⊥}) \cap R_{s u p p (v) \cup {i}}^{I \cup {i}}$ . By our assumption that $s u p p (v) \in C_{π_{I} (W)}$ , we see that $v \in π_{I} (V)$ and that any $v^{'} \in V$ satisfies $v_{I}^{'} \in R v$ . From here, it is easy to check that $dim (V) \in {1, 2}$ and that $dim (V) = 1$ iff $e_{i} \notin V$ . If $dim (V) = 1$ , there is a unique such $v^{'} \in V$ satisfying $v_{I}^{'} = v$ . For this $v^{'}$ , we thus have $s u p p (v^{'}) \in C_{π_{I \cup {i}} (W^{⊥})}$ and we are done. If $dim (V) = 2$ , the choice of $v^{'}$ is not unique. In this case, since $e_{i} \in V$ , we may choose $v^{'}$ so that $(v_{I}^{'}, v_{i}^{'}) = (v_{I}, 0)$ . For this choice, $s u p p (v^{'}) = s u p p (v)$ and $dim (π_{I \cup {i}} (W^{⊥}) \cap R_{s u p p (v)}^{I \cup {i}}) = 1$ . In particular, $s u p p (v^{'}) \in C_{π_{I \cup {i}} (W^{⊥})}$ as needed.

Let $v \in C_{W^{⊥}}$ denote circuit solution obtained by this procedure. Clearly,

κ_{j i}^{W^{⊥}} \geq ∣ ∣ ∣ \frac{v_{i}}{v_{j}} ∣ ∣ ∣ = ∣ ∣ ∣ \frac{h_{i}}{} h_{j} ∣ ∣ ∣ = ∣ ∣ ∣ \frac{g_{j}}{g_{i}} ∣ ∣ ∣ = κ_{i j}^{W} .

By swapping the role of $W$ and $W^{⊥}$ and $i$ and $j$ , we obtain $κ_{i j}^{W} \geq κ_{j i}^{W^{⊥}}$ . The statement follows. ∎

The next theorem relates the circuit imbalance $κ_{W}$ and the condition number ${¯ χ}_{W}$ . The lower bound was already proven in [Vav94], and the upper bound is new, as far as we know.

Theorem 2.9.

For a linear subspace $W \subseteq R^{n}$ ,

\sqrt{1 + (κ_{W})^{2}} \leq {¯ χ}_{W} \leq \sqrt{1 + (n κ_{W})^{2}} .

Proof.

For the first inequality, let $C \in C_{W}$ be the circuit, $i \neq j \in C$ s.t. $| g_{j} / g_{i} | = κ_{W}$ for the corresponding solution $g = g^{C}$ . Let us use the characterization of ${¯ χ}_{W}$ in Proposition 2.4. Let $I = ([n] ∖ C) \cup {i}$ , and $p = g_{i} e^{i}$ , that is, the vector with $p_{i} = g_{i}$ and $p_{k} = 0$ for $k \neq i$ . Then, the unique vector $z \in W$ such that $z_{I} = p$ is $z = g$ . Therefore,

{¯ χ}_{W} \geq min z \in W, z_{I} = p \frac{∥ z ∥}{∥ p ∥} = \frac{∥ g ∥}{| g_{i} |} \geq \frac{\sqrt{| g_{i} |^{2} + | g_{j} |^{2}}}{| g_{i} |} = \sqrt{1 + κ_{W}^{2}} .

The reverse direction is immediate from Lemma 2.11 below. ∎

The next lemmas complete the proof of Theorem 2.9, and will also be used later in the algorithm. Let us say that the vector $y \in R^{n}$ is sign-consistent with $x \in R^{n}$ if $x_{i} y_{i} \geq 0$ for all $i \in [n]$ and $x_{i} = 0$ implies $y_{i} = 0$ for all $i \in [n]$ .

Lemma 2.10.

For $i \in I \subset [n]$ with $e^{i} \in π_{I} (W)$ , let $z = L_{I}^{W} (e^{i})$ . Then for any $j \in s u p p (z)$ we have $κ_{i j}^{W} \geq | z_{j} |$ .

Proof.

We consider the cone $F \subset W$ of vectors sign-consistent with $z$ . The faces of $F$ are bounded by inequalities of the form $z_{k} y_{k} \geq 0$ or $y_{k} = 0$ . The edges (rays) of $F$ are of the form ${α g : α \geq 0}$ with $s u p p (g) \in C_{W}$ . It is easy to see from the Minkowski-Weyl theorem that $z$ can be written as

z = h \sum k = 1 g^{k},

where $h \leq n$ , $C_{1}, C_{2}, \dots, C_{h} \in C_{W}$ are circuits, and the vectors $g^{1}, g^{2}, \dots, g^{h} \in W$ are sign-consistent with $z$ and $s u p p (g^{k}) = C_{k}$ for all $k \in [h]$ . Note that $i \in C_{k}$ for all $k \in [h]$ , as otherwise, $z^{'} = z - g^{k}$ would also satisfy $z_{I}^{'} = e^{i}$ , but $∥ z^{'} ∥ < ∥ z ∥$ due to $g^{k}$ being sign-consistent with $z$ , a contradiction to the definition of $z$ .

At least one $k \in [h]$ contributes at least as much to $| z_{j} | = \frac{\sum_{k = 1}^{h} | g_{j}^{k} |}{\sum_{k = 1}^{h} g_{i}^{k}}$ as average. Hence we find $κ_{i j}^{W} \geq | g_{j}^{k} / g_{i}^{k} | \geq | z_{j} |$ . ∎

For the next lemma, recall the definition of the lifting score $ℓ^{W} (I)$ from (4).

Lemma 2.11.

For a linear subspace $W \subseteq R^{n}$ and an index set $I \subseteq [n]$ , we can efficiently identify $i \in I, j \in [n] ∖ I$ and $t \leq κ_{i j}^{W}$ such that $ℓ^{W} (I) \leq n t$ .

Proof.

Take any minimal $I^{'} \subset I$ such that $dim (π_{I^{'}} (W)) = dim (π_{I} (W))$ . Then we know that $π_{I^{'}} (W) = R^{I^{'}}$ and for $p \in π_{I} (W)$ we can compute $L_{I}^{W} (p) = L_{I^{'}}^{W} (p_{I^{'}})$ . Let $B \in R^{([n] ∖ I) \times I^{'}}$ be the matrix sending any $q \in π_{I^{'}} (W)$ to the corresponding vector $(L_{I^{'}}^{W} (q))_{[n] ∖ I}$ . The column $B_{i}$ can be computed as $(L_{I^{'}}^{W} (e^{i}))_{[n] ∖ I}$ for $e^{i} \in R^{I^{'}}$ . We have $∥ L_{I}^{W} (p) ∥^{2} = ∥ p ∥^{2} + ∥ (L_{I^{'}}^{W} (p_{I^{'}}))_{[n] ∖ I} ∥^{2} \leq ∥ p ∥^{2} + ∥ B ∥^{2} ∥ p_{I^{'}} ∥^{2}$ for any $p \in π_{I} (W)$ , and so $ℓ^{W} (I) = \sqrt{∥ L_{I}^{W} ∥^{2} - 1} \leq ∥ B ∥$ . We upper bound the operator norm by the Frobenius norm $∥ B ∥ \leq ∥ B ∥_{F} = \sqrt{\sum_{j i} B_{j i}^{2}} \leq n {max}_{j i} | B_{j i} |$ . By Lemma 2.10 it follows that $| B_{j i} | = | (L_{I^{'}}^{W} (e^{i}))_{j} | \leq κ_{i j}^{W}$ . ∎

Our LLS algorithm in Section 3 will use the subroutine described in the proof of Lemma 2.11. For a subspace $W \subseteq R^{n}$ , an index set $I \subseteq [n]$ , and a threshold $θ > 0$ , the algorithm Verify-Lift( $W, I, θ$ ) outputs either of the answers ‘pass’ or ’fail’. If the answer is ‘pass’, then it is guaranteed that $ℓ^{W} (I) \leq θ$ . If the answer is ‘fail’, then a pair of indices $i \in I$ , $j \in [n] ∖ I$ , and a bound $t$ are returned, such that $θ / n \leq t \leq κ_{i, j}^{W}$ .

To implement the algorithm, we first need to select a minimal $I^{'} \subset I$ such that $dim (π_{I^{'}} (W)) = dim (π_{I} (W))$ . This can be found by computing a matrix $M \in R^{(n - m) \times n}$ such that $r a n g e (M) = W$ , and selecting a maximal number of linearly independent columns of $M_{I}$ . Then, we compute the matrix $B \in R^{([n] ∖ I) \times I^{'}}$ that implements the transformation $[L_{I^{'}}^{W}]_{[n] ∖ I} : π_{I^{'}} (W) \to π_{[n] ∖ I} (W)$ . The algorithm returns the pair $(i, j)$ corresponding to the entry maximizing $| B_{j i} |$ .

Remark 2.12.

We note that the algorithm Verify-Lift does not need to compute the circuit as in Lemma 2.10. The following observation will be important in the analysis: the algorithm returns the answer ‘fail’ even if $ℓ^{W} (I) \leq θ$ , but $θ < n | B_{j i} |$ .

2.2 A min-max theorem on $κ_{W}^{*}$

We next provide a combinatorial min-max characterization on $κ_{W}^{*}$ . Consider the circuit ratio digraph $G = ([n], E)$ on the node set $[n]$ where $(i, j) \in E$ if $κ (i, j) > 0$ , that is, there exists a circuit $C \in C$ with $i, j \in C$ . An edge $(i, j) \in E$ is said to have weight $κ_{i j} = κ_{i j}^{W}$ . (Note that $(i, j) \in E$ if and only if $(j, i) \in E$ , but the weight of these two edges can be different.)

Let $H$ be a cycle in $G$ , that is, a sequence of points $i_{1}, i_{2}, \dots, i_{k}, i_{k + 1} = i_{1}$ . We use $| H | = k$ to denote the length of the cycle. (In our terminology, ‘cycles’ always refer to objects in $G$ , whereas ‘circuits’ refer to the minimum supports in $Ker (A)$ .)

We use the notation $κ (H) = κ_{W} (H) = \prod_{j = 1}^{k} κ_{i_{j} i_{j + 1}}^{W}$ . For a vector $d \in R_{+ +}^{n}$ , we let $κ^{d} (H) = κ_{W}^{d} (H) = κ_{W D} (H)$ for $D = Diag (d)$ . A simple but important observation is that such a rescaling does not change the value associated with the cycle, that is,

κ_{W}^{d} (H) = κ_{W} (H) \forall d \in R_{+ +}^{n} % for any cycle H in G .

(7)

We are ready to formulate our theorem.

Theorem 2.13.

For a subspace $W \subset R^{n}$ , we have

κ_{W}^{*} = min d > 0 κ_{W}^{d} = max {κ_{W} (H)^{1 / | H |} : H is a cycle in G} .

Proof.

For the direction $κ_{W} (H)^{1 / | H |} \leq κ_{W}^{*}$ we use (7). Let $d > 0$ be a scaling and $H$ a cycle. We have $κ_{i j}^{d} \leq κ_{W}^{d}$ for every $i, j \in [n]$ , and hence $κ_{W} (H) = κ_{W}^{d} (H) \leq (κ_{W}^{d})^{| H |}$ . Since this inequality holds for every $d > 0$ , it follows that $κ_{W} (H) \leq (κ_{W}^{*})^{| H |}$ .

For the reverse direction, consider the following optimization problem.

\begin{matrix} min & t κ_{i j} d_{j} / d_{i} & \leq t \forall (i, j) \in E d & > 0. \end{matrix}

(8)

Note that any feasible solution $(d, t)$ can be rescaled to a feasible solution $(λ d, t)$ for $λ > 0$ with equal objective value. As such, we can strengthen the condition $d > 0$ to $d \geq 1$ without changing the objective value. This makes it clear that the optimum value is achieved by a feasible solution.

Any rescaling $d > 0$ provides a feasible solution with objective value $κ^{d}$ , which means that the optimal value $t^{*}$ of (8) is $t^{*} = κ^{*}$ . Moreover, (8) can be written as

\begin{matrix} min & s log κ_{i j} + z_{j} - z_{i} & \leq s \forall (i, j) \in E z & \in R^{n} . \end{matrix}

(9)

This is the dual of a minimum-mean cycle problem with respect to the cost function $log (κ_{i j})$ . Therefore, an optimal solution corresponds to the cycle maximizing $\sum_{i j \in H} log κ_{i j} / | H |$ , or in other words, maximizing $κ (H)^{1 / | H |}$ . ∎

The following example shows that $κ^{*} \leq {¯ χ}^{*}$ can be arbitrarily big.

Example 2.14.

Take $W = s p a n ((0, 1, 1, M), (1, 0, M, 1))$ , where $M > 0$ . Then ${2, 3, 4}$ and ${1, 3, 4}$ are circuits with $κ_{34}^{W} ({2, 3, 4}) = M$ and $κ_{43}^{W} ({1, 3, 4}) = M$ . Hence, by Theorem 2.13, we see that $κ^{*} \geq M$ .

The following corollary of Theorem 2.13 particularly useful. It asserts that any arbitrary circuit containing $i$ and $j$ yields a $(κ^{*})^{2}$ approximation to $κ_{i j}$ .

Corollary 2.15.

We are given a linear subspace $W \subseteq R^{n}$ and $i, j \in [n]$ , $i \neq j$ , and a circuit $C \in C_{W}$ with $i, j \in C$ . Let $g \in W$ be the corresponding vector with $s u p p (g) = C$ . Then,

\frac{κ_{i j}^{W}}{{(κ_{W}^{*})}^{2}} \leq \frac{| g_{j} |}{| g_{i} |} \leq κ_{i j}^{W} .

Proof.

The second inequality follows by definition. For the first inequality, note that the same circuit $C$ yields $| g_{i} / g_{j} | \leq κ_{j i}^{W} (C) \leq κ_{j i}^{W}$ . Therefore, $| g_{j} / g_{i} | \geq 1 / κ_{j i}^{W}$ .

From Theorem 2.13 we see that $κ_{i j}^{W} κ_{j i}^{W} \leq (κ_{W}^{*})^{2}$ , giving $1 / κ_{j i}^{W} \geq κ_{i j}^{W} / (κ_{W}^{*})^{2}$ , completing the proof. ∎

2.3 Finding circuits: a detour in matroid theory

We now show how to efficiently obtain a family $^C \subseteq C_{W}$ such that for any $i, j \in [n]$ , $^C$ includes a circuit containing both $i$ and $j$ , provided there exists such a circuit.

We need some simple concepts and results from matroid theory. We refer the reader to [Sch03, Chapter 39] or [Fra11, Chapter 5] for definitions and background. Let $M = ([n], I)$ be a matroid on ground set $[n]$ with independent sets $I \subseteq 2^{V}$ . The rank $r k (S)$ of a set $S \subseteq 2^{[n]}$ is the maximum size of an independent set contained in $S$ . The maximal independent sets are called bases. All bases have the same cardinality $r k ([n])$ .

For the matrix $A \in R^{m \times n}$ , we will work with the linear matroid $M (A) = ([n], I (A))$ , where a subset $I \subseteq [n]$ is independent if the columns ${A_{i} : i \in I}$ are linearly independent. Note that $r k ([n]) = m$ under the assumption that $A$ has full row rank.

The circuits of the matroid are the inclusion-wise minimal non-independent sets. Let $I \in I$ be an independent set, and $i \in [n] ∖ I$ such that $I \cup {i} \notin I$ . Then, there exists a unique circuit $C (I, i) \subseteq I \cup {i}$ that is called the fundamental circuit of $i$ with respect to $I$ . Note that $i \in C (I, i)$ .

The matroid $M$ is separable, if the ground set $[n]$ can be partitioned to two nonempty subsets $[n] = S \cup T$ such that $I \in I$ if and only if $I \cap S, I \cap T \in I$ . In this case, the matroid is the direct sum of its restrictions to $S$ and $T$ . In particular, every circuit is fully contained in $S$ or in $T$ .

For the linear matroid $M (A)$ , separability means that $Ker (A) = Ker (A_{S}) \oplus Ker (A_{T})$ . In this case, solving (LP) can be decomposed into two subproblems, restricted to the columns in $A_{S}$ and in $A_{T}$ , and ${¯ χ}_{A} = max {{¯ χ}_{A_{S}}, {¯ χ}_{A_{T}}}$ .

Hence, we can focus on non-separable matroids. The following characterization is well-known, see e.g. [Fra11, Theorems 5.2.5, 5.2.7–5.2.9]. For a hypergraph $H = ([n], E)$ , we define the underlying graph $H_{G} = ([n], E)$ such that $(i, j) \in E$ if there is a hyperedge $S \in E$ with $i, j \in S$ . That is, we add a clique corresponding to each hyperedge. The hypergraph is called connected if the underlying graph $G = ([n], E)$ is connected.

Proposition 2.16.

For a matroid $M = ([n], I)$ , the following are equivalent:

$M$ is non-separable.
The hypergraph of the circuits is connected.
For any base $B$ of $M$ , the hypergraph formed by the fundamental circuits $C^{B} = {C (B, i) : i \in [n] ∖ B}$ is connected.
For any $i, j \in [n]$ , there exists a circuit containing $i$ and $j$ .

Proof.

The implications a $\Leftrightarrow$ b, c $\Rightarrow$ b, and d $\Rightarrow$ b are immediate from the definitions.

For the implication b $\Rightarrow$ c, assume for a contradiction that the hypergraph of the fundamental circuits with respect to $B$ is not connected. This means that we can partition $[n] = S \cup T$ such that for each $i \in S$ , $C (B, i) \subseteq S$ , and for each $i \in T$ , $C (B, i) \subseteq T$ . Consequently, $r k (S) = | B \cap S |$ , $r k (T) = | B \cap T |$ , and therefore $r k ([n]) = r k (S) + r k (T)$ . It is easy to see that this property is equivalent to separability to $S$ and $T$ ; see e.g. [Fra11, Theorem 5.2.7] for a proof.

Finally, for the implication b $\Rightarrow$ d, consider the undirected graph $([n], E)$ where $(i, j) \in E$ if there is a circuit containing both $i$ and $j$ . This graph is transitive according to [Fra11, Theorem 5.2.5]: if $(i, j), (j, k) \in E$ , then also $(i, k) \in E$ . Consequently, whenever $([n], E)$ is connected, it must be a complete graph. ∎

We now give a different proof of c $\Rightarrow$ d that will be convenient for our algorithmic purposes. First, we need a simple lemma that is commonly used in matroid optimization, see e.g. [Fra11, Lemma 13.1.11] or [Sch03, Theorem 39.13].

Lemma 2.17.

Let $I$ be an independent set of a matroid $M = ([n], I)$ , and $U = {u_{1}, u_{2}, \dots, u_{ℓ}} \subseteq I$ , $V = {v_{1}, v_{2}, \dots, v_{ℓ}} \subseteq [n] ∖ I$ such that $I \cup {v_{i}}$ is dependent for each $i \in [ℓ]$ . Further, assume that for each $t \in [ℓ]$ , $u_{t} \in C (I, v_{t})$ and $u_{t} \notin C (I, v_{h})$ for all $h < t$ . Then, $(I ∖ U) \cup V \in I$ .

To prove the lemma, one simply shows that exchanging $v_{t}$ for $u_{t}$ maintains independence, after which one applies induction on $t$ . Based on this lemma, we show the following exchange property.

Lemma 2.18.

Let $B$ be a basis of the matroid $M = ([n], I)$ , and let $U = {u_{1}, u_{2}, \dots, u_{ℓ}} \subseteq B$ , and $V = {v_{1}, v_{2}, \dots, v_{ℓ}, v_{ℓ + 1}} \subseteq [n] ∖ B$ . Assume $C (B, v_{1}) \cap U = {u_{1}}$ , $C (B, v_{ℓ + 1}) \cap U = {u_{ℓ}}$ , and for each $2 \leq t \leq ℓ$ , $C (B, v_{t}) \cap U = {u_{t - 1}, u_{t}}$ . Then $(B ∖ U) \cup V$ contains a unique circuit $C$ , and $V \subseteq C$ .

The situation described here corresponds to a minimal path in the hypergraph $C^{B}$ of the fundamental circuits with respect to a basis $B$ . The hyperedges $C (B, v_{i})$ form a path from $v_{1}$ to $v_{ℓ + 1}$ such that no shortcut is possible (note that this is weaker than requiring a shortest path).

Proof of Lemma 2.18.

Note that $S = (B ∖ U) \cup V \notin I$ since $| S | > | B |$ and $B$ is a basis. For any $i \in [ℓ + 1]$ , we can use Lemma 2.17 to show that $S ∖ {v_{i}} = (B ∖ U) \cup (V ∖ {v_{i}}) \in I$ (and thus, is a basis). To see this, we apply Lemma 2.17 for the ordered sets $V^{'} = {v_{1}, \dots, v_{i - 1}, v_{ℓ + 1}, v_{ℓ}, \dots, v_{i + 1}}$ and $U^{'} = {u_{1}, \dots, u_{i - 1}, u_{ℓ}, u_{ℓ - 1}, \dots, u_{i}}$ .

Consequently, every circuit in $S$ must contain the entire set $V$ . The uniqueness of the circuit in $S$ follows by the well-known circuit axiom asserting that if $C, C^{'} \in C$ , $C \neq C^{'}$ and $v \in C \cap C^{'}$ , then there exists a circuit $C^{''} \in C$ such that $C^{''} \subseteq (C \cup C^{'}) ∖ {v}$ , contradicting the claim that every circuit in $S$ contains the entire set $V$ . ∎

We are ready to describe the algorithm that will be used to obtain lower bounds on all $κ_{i j}$ values. For a matrix $A \in R^{m \times n}$ , we let Find-Circuits( $A$ ) denote the subroutine described in the lemma for the linear matroid $M (A)$ .

Theorem 2.19.

Given $A \in R^{m \times n}$ , there exists an $O (n^{2} m^{2})$ time algorithm Find-Circuits( $A$ ) that obtains a decomposition of $M (A)$ to a direct sum of non-separable linear matroids, and returns a family $^C$ of circuits such that if $i$ and $j$ are in the same non-separable component, then there exists a circuit in $^C$ containing both $i$ and $j$ . Further, for each $i \neq j$ in the same component, the algorithm returns a value ${^κ}_{i j}$ as the the maximum of $| g_{j} / g_{i} |$ such that $g \in W$ , $s u p p (g) = C$ for some $C \in^C$ containing $i$ and $j$ . For these values, ${^κ}_{i j} \leq κ_{i j} \leq (κ^{*})^{2} {^κ}_{i j}$ .

Proof.

Once we have found the set of circuits $^C$ , and computed ${^κ}_{i j}$ as in the statement, the inequalities ${^κ}_{i j} \leq κ_{i j} \leq (κ^{*})^{2} {^κ}_{i j}$ follow easily. The first inequality is by the definition of $κ_{i j}$ , and the second inequality is from Corollary 2.15.

We now turn to the computation of $^C$ . We first obtain a basis $B \subseteq [n]$ via Gauss-Jordan elimination in time $O (n m^{2})$ . Recall the assumption that $A$ has full row-rank. Let us assume that $B = [m]$ is the set of first $m$ indices. The elimination transforms it to the form $A = (I_{m} | H)$ , where $H \in R^{m \times (n - m)}$ corresponds to the non-basis elements. In this form, the fundamental circuit $C (B, i)$ is the support of the $i$ th column of $A$ together with $i$ for every $m + 1 \leq i \leq n$ . We let $C^{B}$ denote the set of all these fundamental circuits.

We construct an undirected graph $G = (B, E)$ as follows. For each $i \in [n] ∖ B$ , we add a clique between the nodes in $C (B, i) ∖ {i}$ . This graph can be constructed in $O (n m^{2})$ time.

The connected components of $G$ correspond to the connected components of $C^{B}$ restricted to $B$ . Thus, due to the equivalence shown in Proposition 2.16 we can obtain the decomposition by identifying the connected components of $G$ . For the rest of the proof, we assume that the entire hypergraph is connected; connectivity can be checked in $O (m^{2})$ time.

We initialize $^C$ as $C^{B}$ . We will then check all pairs $i, j \in [n]$ , $i \neq j$ . If no circuit $C \in^C$ exists with $i, j \in C$ , then we will add such a circuit to $^C$ as follows.

Assume first $i, j \in [n] ∖ B$ . We can find a shortest path in $G$ between the sets $C (B, i) ∖ {i}$ and $C (B, j) ∖ {j}$ in time $O (m^{2})$ . This can be represented by the sequences of points $V = {v_{1}, v_{2}, \dots, v_{ℓ + 1}} \subseteq [n] ∖ B$ , $v_{1} = i$ , $v_{ℓ + 1} = j$ , and $U = {u_{1}, u_{2}, \dots, u_{ℓ}} \subseteq B$ as in Lemma 2.18. According to the lemma, $S = (B ∖ U) \cup V$ contains a unique circuit $C$ that contains all $v_{t}$ ’s, including $i$ and $j$ .

We now show how this circuit can be identified in $O (m)$ time, along with the vector $g^{C}$ . Let $A_{S}$ be the submatrix corresponding to the columns in $S$ . Since $g = g^{C}$ is unique up to scaling, we can set $g_{v_{1}} = 1$ . Note that for each $t \in [ℓ]$ , the row of $A_{S}$ corresponding to $u_{t}$ contains only two nonzero entries: $A_{u_{t} v_{t}}$ and $A_{u_{t} v_{t + 1}}$ . Thus, the value $g_{v_{1}} = 1$ can be propagated to assigning unique values to $g_{v_{2}}, g_{v_{3}}, \dots, g_{v_{ℓ + 1}}$ . Once these values are set, there is a unique extension of $g$ to the indices $t \in B \cap S$ in the basis. Thus, we have identified $g$ as the unique element of $Ker (A_{S})$ up to scaling. The circuit $C$ is obtained as $s u p p (g)$ . Clearly, the above procedure can be implemented in $O (m)$ time.

The argument easily extends to finding circuits for the case ${i, j} \cap B \neq \emptyset$ . If $i \in B$ , then for any choice of $V = {v_{1}, v_{2}, \dots, v_{ℓ + 1}}$ and $U = {u_{1}, u_{2}, \dots, u_{ℓ}}$ as in Lemma 2.18 such that $i \in C (B, v_{1})$ and $i \notin C (B, v_{t})$ for $t > 1$ , the unique circuit in $(B ∖ U) \cup V$ also contains $i$ . This follows from Lemma 2.17 by taking $V^{'} = {v_{ℓ + 1}, v_{ℓ}, \dots, v_{1}}$ and $U^{'} = {u_{ℓ}, \dots, u_{1}, i}$ , which proves that $S ∖ {i} = (B ∖ U^{'}) \cup V^{'} \in I$ . Similarly, if $j \in B$ with $j \in C (B, v_{ℓ + 1})$ and $j \notin C (B, v_{t})$ for $t < ℓ + 1$ , taking $V^{''} = V$ and $U^{''} = {u_{1}, \dots, u_{ℓ}, j}$ gives $S ∖ {j} \in I$ .

The bottleneck for the running time is finding the shortest paths for the $n (n - 1)$ pairs, in time $O (m^{2})$ each. ∎

The triangle inequality

An interesting additional fact about the circuit ratio graph is that the logarithm of the weights satisfy the triangle inequality. The proof uses similar arguments as the proof of Theorem 2.19 above.

Lemma 2.20.

For any distinct $i, j, k$ in the same connected component of $C_{W}$ , and any $g^{C}$ with $i, j \in C$ , $C \in C_{W}$ , there exist circuits $C_{1}, C_{2} \in C_{W}$ , $i, k \in C_{1}$ , $j, k \in C_{2}$ such that $| g_{j}^{C} / g_{i}^{C} | = | g_{j}^{C_{2}} / g_{k}^{C_{2}} | \cdot | g_{k}^{C_{1}} / g_{i}^{C_{1}} |$ .
For any distinct $i, j, k$ in the same connected component of $C_{W}$ , $κ_{i j} \leq κ_{i k} \cdot κ_{k j}$ .

Proof.

Note that part (ii) immediately follows from part (i) when taking $C \in C_{W}$ such that $κ_{i j} (C) = κ_{i j}$ . We now prove part (i).

Let $A \in R^{m \times n}$ be a full-rank matrix with $W = Ker (A)$ . If $C = {i, j}$ , then the columns $A_{i}, A_{j}$ are linearly dependent. Writing $A_{i} = λ A_{j}$ , we have $λ = - g_{j}^{C} / g_{i}^{C}$ . Let $h$ be any circuit solution with $i, k \in s u p p (h)$ , and hence $j \notin s u p p (h)$ . By assumption, the vector $h^{'} = h - h_{i} e_{i} + λ h_{i} e_{j}$ will satisfy $A h^{'} = 0$ and have $i \notin s u p p (h^{'}), j, k \in s u p p (h^{'})$ . We know that $h^{'}$ is a circuit solution, because any circuit $C^{'} \subset s u p p (h^{'})$ could, by the above process in reverse, be used to produce a kernel solution with strictly smaller support than $h$ , contradicting the assumption that $h$ is a circuit solution. Now we have $| h_{j}^{'} / h_{k}^{'} | \cdot | h_{k} / h_{i} | = | h_{j}^{'} / h_{i} | = | λ |$ by construction. Thus, $h$ and $h^{'}$ are the circuit solutions we are looking for.

Now assume $C \neq {i, j}$ . If $k \in C$ , the statement is trivially true with $C = C_{1} = C_{2}$ , so assume $k \notin C$ . Pick $l \in C$ , $l \notin {i, j}$ and set $B = C ∖ {l}$ . Assume without loss of generality that $B \subseteq [m]$ and apply row operations to $A$ such that $A_{B, B} = I_{B \times B}$ is an identity submatrix and $A_{[n] ∖ B, B} = 0$ . Then the column $A_{l}$ has support given by $B$ , for otherwise $g^{C}$ could not be in the kernel. The given circuit solution satisfies $g_{t}^{C} = - A_{t, l} g_{l}^{C}$ for all $t \in B$ , and in particular $g_{j}^{C} / g_{i}^{C} = A_{j, l} / A_{i, l}$ .

Take any minimal set $J \subset [n]$ such that $k \in J$ and the linear matroid induced by $C \cup J$ is non-separable. We show that we can uniquely lift any vector $x \in Ker (A_{B, C \cup {k}})$ to a vector $x^{'} \in Ker (A_{C \cup J}), x_{C \cup k}^{'} = x$ . Since this lift will send circuit solutions to circuit solutions by uniqueness, it suffices to find our desired circuits as solutions to the smaller linear system.

Consider a circuit solution $h \in W$ such that ${l, k} \subset s u p p (h) \subset C \cup J$ , which exists by Proposition 2.16 d. Minimality of $J$ and Proposition 2.16 b imply $J \subset s u p p (h)$ . This $h$ gives rise to the non-zero vector $h_{J} \in Ker (A_{[n] ∖ B, J})$ . Moreover, $dim (Ker (A_{[n] ∖ B, J})) = 1$ , as $J \subset s u p p (h) \subset J \cup C, A_{[n] ∖ B, C} = 0$ and minimality of $J$ . This provides us with clear linear relations between any two entries in $J$ of any vector in $Ker (A_{[n] ∖ B, J})$ , implying that we can apply row operations to $A$ such that $A_{B, J}$ has non-zero entries only in the column $A_{B, {k}}$ . Note that these row operations leave $A_{C}$ unchanged. From this, we can see that any element in $Ker (A_{B, C \cup {k}})$ can be uniquely lifted to an element in $Ker (A_{C \cup J})$ . Hence we can focus on $Ker (A_{B, C \cup {k}})$ .

If $A_{i, k} = A_{j, k} = 0$ , then any $x \in Ker (A_{B, C \cup {k}})$ satisfies $x_{i} + A_{i, l} x_{l} = x_{j} + A_{j, l} x_{l} = 0$ and, in particular, any circuit $l, k \in ¯ C \subset C \cup {k}$ contains ${i, j} \subset ¯ C$ and fulfills $| g_{j}^{C} / g_{i}^{C} | = | A_{j, l} / A_{i, l} | = | g_{j}^{¯ C} / g_{i}^{¯ C} | = | g_{j}^{¯ C} / g_{k}^{¯ C} | | g_{k}^{¯ C} / g_{i}^{¯ C} |$ . Choosing $C_{1} = C_{2} = ¯ C$ concludes the case.

Otherwise, we know that $A_{i, k} \neq 0$ or $A_{j, k} \neq 0$ . Any circuit in $Ker (A_{{i, j}, {i, j, l, k}})$ can be lifted uniquely to an element in $Ker (A_{B, C \cup {k}})$ since $A_{B, B}$ is an identity matrix and we can set the entries of $B ∖ {i, j}$ individually to satisfy the equalities. Note that this lifted vector is a circuit as well. Hence we may restrict our attention to the matrix $A_{{i, j}, {i, j, l, k}}$ . If the columns $A_{{i, j}, k}, A_{{i, j}, l}$ are linearly dependent, then any circuit solution to $A_{{i, j}, {i, j, l}} x = 0, x_{l} \neq 0$ , such as $g_{{i, j, l}}^{C}$ , is easily transformed into a circuit solution to $A_{{i, j}, {i, j, k}} x = 0, x_{k} \neq 0$ and we are done.

If $A_{{i, j}, k}, A_{{i, j}, l}$ are independent, we can write $A_{{i, j}, {i, j, l, k}} = (\begin{matrix} 1 & 0 & a & c 0 & 1 & b & d \end{matrix})$ , where $g_{j}^{C} / g_{i}^{C} = b / a$ . For $α = a d - b c$ , which is non-zero since $α = det ((\begin{matrix} a & c b & d \end{matrix})) \neq 0$ by the independence assumption, we observe that $(α, 0, - d, b)$ and $(0, α, c, - a)$ are the circuits we are looking for. ∎

2.4 Approximating $¯ χ$ and ${¯ χ}^{*}$

Equipped with Theorem 2.13 and Theorem 2.19, we are ready to prove Theorem 2.5, that is, given $A \in R^{m \times n}$ , find an approximately optimal rescaling $D \in D$ of the columns. Recall that we defined $κ_{i j}^{d} := κ_{i j}^{W D} = κ_{i j} d_{j} / d_{i}$ when $d > 0$ . We can similarly define ${^κ}_{i j}^{d} := {^κ}_{i j} d_{j} / d_{i}$ , and ${^κ}_{i j}^{d}$ approximates $κ_{i j}^{d}$ just as in Theorem 2.19.

Proof of Theorem 2.5.

Let us run the algorithm Finding-Circuits $(A)$ described in Theorem 2.19 to obtain the values ${^κ}_{i j}$ such that ${^κ}_{i j} \leq κ_{i j} \leq (κ_{W}^{*})^{2} {^κ}_{i j}$ . We let $G = ([n], E)$ be the circuit ratio digraph, that is, $(i, j) \in E$ if $κ_{i j} > 0$ .

To show the first statement on approximating $¯ χ$ , we simply set $t = \sqrt{1 + {max}_{(i, j) \in E} {^κ}_{i j}^{2}}$ . Then, $t \leq {¯ χ}_{W} \leq t n ({¯ χ}_{W}^{*})^{2}$ follows by Theorem 2.9.

For the second statement on finding a nearly optimal rescaling for ${¯ χ}_{W}^{*}$ , we consider the following optimization problem, which is an approximate version of (8) from Theorem 2.13.

\begin{matrix} min & t {^κ}_{i j} d_{j} / d_{i} & \leq t \forall (i, j) \in E d & > 0. \end{matrix}

(10)

Let $^d$ be an optimal solution to (10) with value $^t$ . We will prove that $κ^{^d} \leq (κ_{W}^{*})^{3}$ .

First, observe that $κ_{i j}^{^d} = κ_{i j} {^d}_{j} / {^d}_{i} \leq (κ_{W}^{*})^{2} {^κ}_{i j} {^d}_{j} / {^d}_{i} \leq (κ_{W}^{*})^{2}^t$ for any $(i, j) \in E$ . Now, let $d^{*} > 0$ be such that $κ^{d^{*}} = κ_{W}^{*}$ . The vector $d^{*}$ is a feasible solution to (10), and so $^t \leq {max}_{i \neq j} {^κ}_{i j} d_{j}^{*} / d_{i}^{*} \leq {max}_{i \neq j} κ_{i j} d_{j}^{*} / d_{i}^{*} = κ^{d^{*}}$ . Hence we find that $^d$ gives a rescaling with ${¯ χ}_{W ˆ D} \leq \sqrt{1 + (n κ^{^d})^{2}} \leq \sqrt{1 + (n (κ_{W}^{*})^{3})^{2}}$ .

Using Theorem 2.9, we show that $\sqrt{1 + (n (κ_{W}^{*})^{3})^{2}} \leq n ({¯ χ}_{W}^{*})^{3}$ . Indeed,

n ({¯ χ}_{W}^{*})^{3} \geq n {(\sqrt{1 + (κ_{W}^{*})^{2}})}^{3} \geq n \sqrt{1 + (κ_{W}^{*})^{6}} \geq \sqrt{1 + (n (κ_{W}^{*})^{3})^{2}} .

We can obtain the optimal value $^t$ of (10) by solving the corresponding maximum-mean cycle problem (see Theorem 2.13). It is easy to develop a multiplicative version of the standard dynamic programming algorithm of the classical minimum-mean cycle problem (see e.g. [AMO93, Theorem 5.8]) that allows finding the optimum to (10) directly, in the same $O (n^{3})$ time.

It is left to find the labels $d_{i} > 0$ , $i \in [n]$ such that ${^κ}_{i j} d_{j} / d_{i} \leq^t$ for all $(i, j) \in E$ . We define the following weighted directed graph. We associate the weight $w_{i j} = log^t - log {^κ}_{i j}$ with every $(i, j) \in E$ , and add an extra source vertex $r$ with edges $(r, i)$ of weight $w_{r i} = 0$ for all $i \in [n]$ .

By the choice of $^t$ , this graph does not contain any negative weight directed cycles. We can compute the shortest paths from $r$ to all nodes in $O (n^{3})$ using the Bellman-Ford algorithm; let $σ_{i}$ be the shortest path label for $i$ . We then set $d_{i} = exp (σ_{i})$ .

The running time of the whole algorithm will be bounded by $O (n^{2} m^{2} + n^{3})$ . The running time is dominated by the $O (n^{2} m^{2})$ complexity of Finding-Circuits $(A)$ and the $O (n^{3})$ complexity of solving the minimum-mean cycle problem and shortest path computation. ∎

3 A scaling-invariant layered least squares interior-point algorithm

3.1 Preliminaries on interior-point methods

In this section, we introduce the standard definitions, concepts and results from the interior-point literature that will be required for our algorithm. We consider an LP problem in the form (LP), or equivalently, in the subspace form (2) for $W = Ker (A)$ . We let

P^{+ +} = {x \in R^{n} : A x = b, x > 0}, D^{+ +} = {(y, s) \in R^{m + n} : A^{⊤} y + s = c, s > 0} .

Recall the central path defined in (CP), with $w (μ) = (x (μ), y (μ), s (μ))$ denoting the central path point corresponding to $μ > 0$ . We let $w^{*} = (x^{*}, y^{*}, s^{*})$ denote the primal and dual optimal solutions to (LP) that correspond to the limit of the central path for $μ \to 0$ .

For a point $w = (x, y, s) \in P^{+ +} \times D^{+ +}$ , the normalized duality gap is $μ (w) = x^{⊤} s / n$ .

The $ℓ_{2}$ -neighborhood of the central path with opening $β > 0$ is the set

N (β)

= {w \in P^{+ +} \times D^{+ +} : ∥ ∥ ∥ \frac{x s}{μ (w)} - e ∥ ∥ ∥ \leq β}

Throughout the paper, we will assume $β$ is chosen from $(0, 1 / 4]$ ; in Algorithm 2 we use the value $β = 1 / 8$ . The following proposition gives a bound on the distance between $w$ and $w (μ)$ if $w \in N (β)$ . See e.g. [Gon92, Lemma 5.4].

Proposition 3.1.

Let $w = (x, y, s) \in N (β)$ for $β \in (0, 1 / 4]$ and $μ = μ (w)$ , and consider the central path point $w (μ) = (x (μ), y (μ), s (μ))$ . For each $i \in [n]$ ,

	$\frac{x_{i}}{1 + 2 β} \leq \frac{1 - 2 β}{1 - β} \cdot x_{i}$	$\leq x_{i} (μ) \leq \frac{x_{i}}{1 - β}, and$
	$\frac{s_{i}}{1 + 2 β} \leq \frac{1 - 2 β}{1 - β} \cdot s_{i}$	$\leq s_{i} (μ) \leq \frac{s_{i}}{1 - β} .$

We will often use the following immediate corollary.

Corollary 3.2.

Let $w = (x, y, s) \in N (β)$ for $β \in (0, 1 / 4]$ , and $μ = μ (w)$ . Then for each $i \in [n]$

(1 - β) \sqrt{μ} \leq \sqrt{s_{i} x_{i}} \leq (1 + 2 β) \sqrt{μ} .

A key property of the central path is “near monotonicity”, formulated in the following lemma, see [VY96, Lemma 16].

Lemma 3.3.

Let $w = (x, y, s)$ be a central path point for $μ$ and $w^{'} = (x^{'}, y^{'}, s^{'})$ be a central path point for $μ^{'} \leq μ$ . Then $∥ x^{'} / x + s^{'} / s ∥_{\infty} \leq n$ . Further, for the optimal solution $w^{*} = (x^{*}, y^{*}, s^{*})$ corresponding to the central path limit $μ \to 0$ , we have $∥ x^{*} / x ∥_{1} + ∥ s^{*} / s ∥_{1} = n$ .

Proof.

We now show $∥ x^{'} / x ∥_{1} + ∥ s^{'} / s ∥_{1} \leq 2 n$ and the second statement. For $∥ x^{'} / x + s^{'} / s ∥_{\infty} \leq n$ , see the proof of [VY96, Lemma 16]. Since $x - x^{'} \in W$ and $s - s^{'} \in W^{⊥}$ , we have $(x - x^{'})^{⊤} (s - s^{'}) = 0$ . This can be rewritten as $x^{⊤} s^{'} + (x^{'})^{⊤} s = x^{⊤} s + (x^{'})^{⊤} s^{'}$ . The right hand side equals $n μ + n μ^{'}$ . Dividing by $μ$ , and noting that $x_{i} s_{i} = μ$ for all $i \in [n]$ , we obtain

{∥ ∥ ∥ \frac{x^{'}}{x} ∥ ∥ ∥}_{1} + {∥ ∥ ∥ \frac{s^{'}}{s} ∥ ∥ ∥}_{1} = n \sum i = 1 \frac{x_{i}^{'}}{x_{i}} + \frac{s_{i}^{'}}{s_{i}} = n (1 + \frac{μ^{'}}{μ}) .

Hence $∥ x^{'} / x ∥ + ∥ s^{'} / s ∥_{1} \leq 2 n$ by $μ^{'} \leq μ$ . We get the second statement by taking the limit $μ^{'} \to 0$ . ∎

3.2 Predictor and corrector steps

Given $w = (x, y, s) \in P^{+ +} \times D^{+ +}$ , the search directions commonly used in interior-point methods are obtained as the solution $(Δ x, Δ y, Δ s)$ to the following linear system for some $σ \in [0, 1]$ .

$A Δ x$	$= 0$	(11)
$A^{⊤} Δ y + Δ s$	$= 0$	(12)
$s Δ x + x Δ s$	$= σ μ e - x s$	(13)

Predictor-corrector methods, such as the Mizuno-Todd-Ye Predictor-Corrector (MTY P-C) algorithm [MTY93], alternate between two types of steps. In predictor steps, we use $σ = 0$ . This direction is also called the affine scaling direction, and will be denoted as $Δ w^{a} = (Δ x^{a}, Δ y^{a}, Δ s^{a})$ throughout. In corrector steps, we use $σ = 1$ . This gives the centrality direction, denoted as $Δ w^{c} = (Δ x^{c}, Δ y^{c}, Δ s^{c})$ .

In the predictor steps, we make progress along the central path. Given the search direction on the current iterate $w = (x, y, s) \in N (β)$ , the step-length is chosen maximal such that we remain in $N (2 β)$ , i.e.

α^{a} := sup {α \in [0, 1] : \forall α^{'} \in [0, α] : w + α^{'} Δ w^{a} \in N (2 β)} .

Thus, we obtain a point $w^{+} = w + α^{a} Δ w^{a} \in N (2 β)$ . The corrector step finds a next iterate $w^{c} = w^{a} + Δ w^{c}$ , where $Δ w^{c}$ is the centrality direction computed at $w^{a}$ . The next proposition summarizes well-known properties, see e.g. [Ye97, Section 4.5.1].

Proposition 3.4.

Let $w = (x, y, s) \in N (β)$ for $β \in (0, 1 / 4]$ .

For the affine scaling step, we have $μ (w^{+}) = (1 - α) μ (w)$ .
The affine scaling step-length is

$α^{a} \geq max {\frac{β}{\sqrt{n}}, 1 - \frac{∥ Δ x^{a} Δ s^{a} ∥}{β μ (w)}} .$
For $w^{+} \in N (2 β)$ , and $w^{c} = w^{+} + Δ w^{c}$ , we have $μ (w^{c}) = μ (w^{+})$ and $w^{c} \in N (β)$ .
After a sequence of $O (\sqrt{n} t)$ predictor and corrector steps, we obtain an iterate $w^{'} = (x^{'}, y^{'}, s^{'}) \in N (β)$ such that $μ (w^{'}) \leq μ (w) / 2^{t}$ .

Minimum norm viewpoint and residuals

For any point $w = (x, y, s) \in P^{+ +} \times D^{+ +}$ we define

δ = δ (w) = s^{1 / 2} x^{- 1 / 2} \in R^{n} .

(14)

With this notation, we can write (13) in the form

δ Δ x + δ^{- 1} Δ s = - s^{1 / 2} x^{1 / 2} .

(15)

From Proposition 3.1, we see that if $w \in N (β)$ , and $μ = μ (w)$ , then for each $i \in [n]$ ,

\sqrt{1 - 2 β} \cdot δ_{i} (w) \leq δ_{i} (w (μ)) \leq \frac{1}{\sqrt{1 - 2 β}} \cdot δ_{i} (w) .

(16)

The matrix $Diag (δ (w))$ will be often used for rescaling in the algorithm. That is, for the current iterate $w = (x, y, s)$ in the interior-point method, we will perform projections in the space $W Diag (δ (w))$ . To simplify notation, for $δ = δ (w)$ , we use $L_{I}^{δ}$ and $κ_{i j}^{δ}$ as shorthands for $L_{I}^{W Diag (δ)}$ and $κ_{i j}^{W Diag (δ)}$ . The subspace $W = Ker (A)$ will be fixed throughout.

It is easy to see from the optimality conditions that the components of the affine scaling direction $(Δ x^{a}, Δ y^{a}, Δ s^{a})$ are the optimal solutions of the following minimum-norm problems.

	$Δ x^{a}$	$= a r g m i n Δ x \in R^{n} {∥ δ (x + Δ x) ∥^{2} : A Δ x = 0}$		(17)
	$(Δ y^{a}, Δ s^{a})$	$= a r g m i n (Δ y, Δ s) \in R^{m} \times R^{n} {∥ δ^{- 1} (s + Δ s) ∥^{2} : A^{⊤} Δ y + Δ s = 0}$		(17)

Following [MT05], for a search direction $Δ w = (Δ x, Δ y, Δ s)$ , we define the residuals as

R x

:= \frac{δ (x + Δ x)}{\sqrt{μ}},

R s

:= \frac{δ^{- 1} (s + Δ s)}{\sqrt{μ}} .

(18)

Hence, the primal affine scaling direction $Δ x^{a}$ is the one that minimizes the $ℓ_{2}$ -norm of the primal residual $R x$ , and the dual affine scaling direction $(Δ y^{a}, Δ s^{a})$ minimizes the $ℓ_{2}$ -norm of the dual residual $R s$ . The next lemma summarizes simple properties of the residuals, see [MT05].

Lemma 3.5.

For $β \in (0, 1 / 4]$ such that $w = (x, y, s) \in N (β)$ and the affine scaling direction $Δ w = (Δ x^{a}, Δ y^{a}, Δ s^{a})$ , we have

$R x^{a} R s^{a} = \frac{Δ x^{a} Δ s^{a}}{μ}, R x^{a} + R s^{a} = \frac{x^{1 / 2} s^{1 / 2}}{\sqrt{μ}},$ (19)
$∥ R x^{a} ∥^{2} + ∥ R s^{a} ∥^{2} = n,$
We have $∥ R x^{a} ∥, ∥ R s^{a} ∥ \leq \sqrt{n}$ , and for each $i \in [n]$ , $max {| R x_{i}^{a} |, | R s_{i}^{a} |} \geq \frac{1}{2} (1 - β)$ .
$R x^{a} = - \frac{1}{\sqrt{μ}} δ^{- 1} Δ s^{a}, R s^{a} = - \frac{1}{\sqrt{μ}} δ Δ x^{a} .$

Proof.

Parts a, b, d are immediate from the definitions and from (11)-(13). In part c, the first statement follows by part b, noting that ${R x^{a}}^{⊤} R s^{a} = 0$ . The second statement follows from a and Corollary 3.2. ∎

For a subset $I \subset [n]$ , we define

ε_{I}^{a} (w) := max i \in I min {| R x_{i}^{a} |, | R s_{i}^{a} |}, and ε^{a} (w) := ε_{[n]}^{a} (w) .

(20)

The next claim shows that for the affine scaling direction, a small $ε (w)$ yields a long step; see [MT05, Lemma 2.5].

Lemma 3.6.

Let $w = (x, y, s) \in N (β)$ for $β \in (0, 1 / 4]$ . Then for the affine scaling step, we have

\frac{μ (w + α^{a} Δ w^{a})}{μ (w)} \leq min {1 - \frac{β}{\sqrt{n}}, \frac{\sqrt{n} ε^{a} (w)}{β}} .

Proof.

Let $ε := ε^{a} (w)$ . From Lemma 3.5 a, we get $∥ Δ x^{a} Δ s^{a} ∥ / μ = ∥ R x^{a} R s^{a} ∥$ . We can bound $∥ R x^{a} R s^{a} ∥ \leq ε (∥ R x^{a} ∥ + ∥ R s^{a} ∥) \leq ε \sqrt{n}$ , where the latter inequality follows by Lemma 3.5 c. From Proposition 3.4 b, we get $α^{a} \geq max {β / \sqrt{n}, 1 - \sqrt{n} ε / β}$ . The claim follows by part a of the same proposition. ∎

3.3 Layered-least-squares direction

Let $J = (J_{1}, J_{2}, \dots, J_{p})$ be an ordered partition of $[n]$ .¹¹1In contrast to how ordered partitions were defined in [MT05], we use the term ordered only to the $p$ -tuple $(J_{1}, \dots, J_{p})$ , which is to be viewed independently of $δ$ . For $k \in [p]$ , we use the notations $J_{< k} := J_{1} \cup \dots \cup J_{k - 1}$ , $J_{> k} := J_{k + 1} \cup \dots \cup J_{p}$ , and similarly $J_{\leq k}$ and $J_{\geq k}$ . We will also refer to the sets $J_{k}$ as layers, and $J$ as a layering. Layers with lower indices will be referred to as ’higher’ layers.

Given $w = (x, y, s) \in P^{+ +} \times D^{+ +}$ , and the layering $J$ , the layered-least-squares (LLS) direction is defined as follows. For the primal direction, we proceed backwards, with $k = p, p - 1, \dots, 1$ . Assume the components on the lower layers $Δ x_{J_{> k}}^{l l}$ have already been determined. We define the components in $J_{k}$ as the coordinate projection $Δ x_{J_{k}}^{l l} = π_{J_{k}} (X_{k})$ , where the affine subspace $X_{k}$ is defined as the set of minimizers

X_{k}

:= a r g m i n Δ x \in R^{n} {∥ δ_{J_{k}} (x_{J_{k}} + Δ x_{J_{k}}) ∥^{2} : A Δ x = 0, Δ x_{J_{> k}} = Δ x_{J_{> k}}^{l l}} .

(21)

The dual direction $Δ s^{l l}$ is determined in the forward order of the layers $k = 1, 2, \dots, p$ . Assume we already fixed the components $Δ s_{J_{< k}}^{l l}$ on the higher layers. Then, $Δ s_{J_{k}}^{l l} = π_{J_{k}} (S_{k})$ for

S_{k}

= a r g m i n Δ s \in R^{n} {∥ δ_{J_{k}}^{- 1} (s_{J_{k}} + Δ s_{J_{k}}) ∥^{2} : \exists y \in R^{m}, A^{⊤} Δ y + Δ s = 0, Δ s_{J_{< k}} = Δ s_{J_{< k}}^{l l}} .

(22)

The component $Δ y^{l l}$ is obtained as the optimal $Δ y$ for the final layer $k = p$ . We use the notation $R x^{l l}$ and $ε^{l l} (w)$ analogously to the affine scaling direction. This search direction was first introduced in [VY96].

The affine scaling direction is a special case for the single element partition. In this case, the definitions (21) and (22) coincide with those in (17).

3.3.1 A linear system viewpoint

We now present an equivalent definition of the LLS step, generalizing the linear system (12)-(13). We use the subspace notation. With this notation, (12)-(13) for the affine scaling direction can be written as

s Δ x^{a} + x Δ s^{a} = - x s, Δ x^{a} \in W, and Δ s^{a} \in W^{⊥} .

(23)

Recall that (23) is equivalent to $δ Δ x^{a} + δ^{- 1} Δ s^{a} = - x^{1 / 2} s^{1 / 2}$ .

Given the layering $J$ and $w = (x, y, s)$ , for each $k \in [p]$ we define the subspaces

W_{J, k} := {x_{J_{k}} : x \in W, x_{J_{> k}} = 0} and W_{J, k}^{⊥} := {x_{J_{k}} : x \in W^{⊥}, x_{J_{< k}} = 0} .

It is easy to see that these two subspaces are orthogonal complements. Analogously to (23), the primal LLS step $Δ x^{l l}$ is obtained as the unique solution to the linear system

δ Δ x^{l l} + δ^{- 1} Δ s = - x^{1 / 2} s^{1 / 2}, Δ x^{l l} \in W, and Δ s \in W_{J, 1}^{⊥} \oplus \dots \oplus W_{J, p}^{⊥},

(24)

and the dual LLS step $Δ s^{l l}$ is the unique solution to

δ Δ x + δ^{- 1} Δ s^{l l} = - x^{1 / 2} s^{1 / 2}, Δ x \in W_{J, 1} \oplus \dots \oplus W_{J, p}, and Δ s^{l l} \in W^{⊥} .

(25)

It is important to note that $Δ s$ in (24) may be different from $Δ s^{l l}$ , and $Δ x$ in (25) may be different from $Δ x^{l l}$ . In fact, $Δ s^{l l} = Δ s$ and $Δ x^{l l} = Δ x$ can only be the case for the affine scaling step.

The following lemma proves that the above linear systems are indeed uniquely solved by the LLS step.

Lemma 3.7.

For $t \in R^{n}$ , $W \subseteq R^{n}$ , $δ \in R_{+ +}^{n}$ , and $J = (J_{1}, J_{2}, \dots, J_{p})$ , let $w = {L L S}_{J}^{W, δ} (t)$ be defined by

δ w + δ^{- 1} v = δ t, w \in W, v \in W_{J, 1}^{⊥} \oplus \dots \oplus W_{J, p}^{⊥} .

Then ${L L S}_{J}^{W, δ} (t)$ is well-defined and

for every $k \in [p]$ .

In the notation of the above lemma we have, for ordered partitions $J = (J_{1}, J_{2}, \dots, J_{p})$ , $¯ J = (J_{p}, J_{p - 1}, \dots, J_{1})$ , and $(x, y, s) \in P^{+ +} \times D^{+ +}$ with $δ = s^{1 / 2} x^{- 1 / 2}$ , that $Δ x^{l l} = {L L S}_{J}^{W, δ} (- x)$ and $Δ s^{l l} = {L L S}_{¯ J}^{W^{⊥}, δ^{- 1}} (- s)$ .

Proof of Lemma 3.7.

We first prove the equality $W \cap (W_{J, 1}^{⊥} \oplus \dots \oplus W_{J, p}^{⊥}) = {0}$ , and by a similar argument we have $W^{⊥} \cap (W_{J, 1} \oplus \dots \oplus W_{J, p}) = {0}$ . By duality, this last equality tells us that

(W^{⊥} \cap (W_{J, 1} \oplus \dots \oplus W_{J, p}))^{⊥} = W + (W_{J, 1}^{⊥} \oplus \dots \oplus W_{J, p}^{⊥}) = R^{n} .

Thus, the linear decomposition defining ${L L S}_{J}^{W, δ} (t)$ has a solution and its solution is unique.

Suppose $y \in W \cap (W_{J, 1}^{⊥} \oplus \dots \oplus W_{J, p}^{⊥})$ . We prove $y_{J_{k}} = 0$ by induction on $k$ , starting at $k = p$ . The induction hypothesis is that $y_{J_{> k}} = 0$ , which is an empty requirement when $k = p$ . The hypothesis $y_{J_{> k}} = 0$ together with the assumption $y \in W$ is equivalent to $y \in W \cap R_{J_{\leq k}}^{n}$ , and implies $y_{J_{k}} \in π_{J_{k}} (W \cap R_{J_{\leq k}}^{n}) := W_{J, k}$ . Since we also have $y_{J_{k}} \in W_{J, k}^{⊥}$ by assumption, which is the orthogonal complement of $W_{J, k}$ , we must have $y_{J_{k}} = 0$ . Hence, by induction $y = 0$ . This finishes the proof that ${L L S}_{J}^{W, δ} (t)$ is well-defined.

Next we prove that $w$ is a minimizer of $min {∥ ∥ δ_{J_{k}} (t_{J_{k}} - z_{J_{k}}) ∥ ∥ : z \in W, z_{J_{> k}} = w_{J_{> k}}}$ . The optimality condition is for $δ_{J_{k}} (t_{J_{k}} - z_{J_{k}})$ to be orthogonal to $δ_{J_{k}} u$ for any $u \in W_{J, k}$ . By the LLS equation, we have $δ_{J_{k}} (t_{J_{k}} - w_{J_{k}}) = δ_{J_{k}}^{- 1} v_{J_{k}}$ , where $v_{J_{k}} \in W_{J, k}^{⊥}$ . Noting then that $⟨ δ_{J_{k}} u, δ_{J_{k}}^{- 1} v ⟩ = ⟨ u_{J_{k}}, v_{J_{k}} ⟩ = 0$ for $u \in W_{J, k}$ , the optimality condition follows immediately. ∎

With these tools, we can prove that the lifting costs are self-dual. This explains the reverse order in the dual vs primal LLS step and justifies our attention on the lifting cost in a self-dual algorithm. The next proposition generalizes the result of [GL97]. Note that it gives a proof of Proposition 2.1 d.

Proposition 3.8.

For a linear subspace $W \subseteq R^{n}$ and index set $I \subseteq [n]$ with $J = [n] ∖ I$ ,

∥ L_{I}^{W} ∥ \leq max {1, ∥ L_{J}^{W^{⊥}} ∥} .

In particular, $ℓ^{W} (I) = ℓ^{W^{⊥}} (J)$ .

Proof.

We first treat the case where $π_{I} (W) = {0}$ or $π_{J} (W^{⊥}) = {0}$ . If $π_{I} (W) = {0}$ then $∥ L_{I}^{W} ∥ = ℓ^{W} (I) = 0$ . Furthermore, in this case $R^{I} = π_{I} (W)^{⊥} = π_{I} (W^{⊥} \cap R_{I}^{n})$ , and thus $π_{R_{J}^{n}} (W^{⊥}) \subseteq W^{⊥}$ . In particular, $∥ L_{J}^{W} ∥ \leq 1$ and $ℓ^{W^{⊥}} (J) = 0$ . Symmetrically, if $π_{J} (W^{⊥}) = {0}$ then $∥ L_{J}^{W^{⊥}} ∥ = ℓ^{W^{⊥}} (J) = 0$ , $∥ L_{I}^{W} ∥ \leq 1$ and $ℓ^{W} (I) = 0$ .

We now restrict our attention to the case where both $π_{I} (W), π_{J} (W^{⊥}) \neq {0}$ . Under this assumption, we show that $∥ L_{I}^{W} ∥ = ∥ L_{J}^{W^{⊥}} ∥$ and thus that $ℓ^{W} (I) = ℓ^{W^{⊥}} (J)$ . Note that by non-emptyness, we clearly have that $∥ L_{I}^{W} ∥, ∥ L_{J}^{W^{⊥}} ∥ \geq 1$ .

We formulate a more general claim. Let ${0} \neq U, V \subset R^{n}$ be linear subspaces such that $U + V = R^{n}$ and $U \cap V = {0}$ . Note that for the orthogonal complements in $R^{n}$ , we also have ${0} \neq U^{⊥}, V^{⊥}$ , $U^{⊥} + V^{⊥} = R^{n}$ and $U^{⊥} \cap V^{⊥} = {0}$ .

Claim 3.9.

Let ${0} \neq U, V \subset R^{n}$ be linear subspaces such that $U + V = R^{n}$ and $U \cap V = {0}$ . Thus, for $z \in R^{n}$ , there are unique decompositions $z = u + v$ with $u \in U$ , $v \in V$ and $z = u^{'} + v^{'}$ with $u^{'} \in U^{⊥}$ and $v^{'} \in V^{⊥}$ . Let $T : R^{n} \to V$ be the map sending $T z = v$ . Let $T^{'} : R^{n} \to V^{⊥}$ be the map sending $T^{'} z = v^{'}$ . Then, $∥ T ∥ = ∥ T^{'} ∥$ .

Proof.

To prove the statement, we claim that it suffices to show that if $∥ T ∥ > 1$ then $∥ T^{'} ∥ \geq ∥ T ∥$ . To prove sufficiency, note that by symmetry, we also get that if $∥ T^{'} ∥ > 1$ then $∥ T ∥ \geq ∥ T^{'} ∥$ . Since $V, V^{⊥} \neq {0}$ by assumption, we always have $∥ T ∥, ∥ T^{'} ∥ \geq 1$ , and thus the equality $∥ T ∥ = ∥ T^{'} ∥$ must hold in all cases. We now assume $∥ T ∥ > 1$ and show $∥ T^{'} ∥ \geq ∥ T ∥$ .

Representing $T$ as an $n \times n$ matrix, we write $T = \sum_{i = 1}^{k} σ_{i} v_{i} u_{i}^{⊤}$ using a singular value decomposition with $σ_{1} \geq \dots \geq σ_{k} > 0$ . As such, $v_{1}, \dots, v_{k}$ is an orthonormal basis of $V$ , since the $r a n g e (T) = V$ , and $u_{1}, \dots, u_{k}$ is an orthonormal basis of $U^{⊥}$ , since $Ker (T) = U$ , noting that we have restricted to the singular vectors associated with positive singular values. By assumption, we have that $∥ T ∥ = ∥ T u_{1} ∥ = σ_{1} > 1$ .

The proof is complete by showing that

∥ ∥ T^{'} (v_{1} - σ_{1}^{- 1} u_{1}) ∥ ∥ \geq σ_{1} ∥ v_{1} - u_{1} / σ_{1} ∥,

(26)

and that $∥ v_{1} - u_{1} / σ_{1} ∥ > 0$ .

The map $T$ is a linear projection with $T^{2} = T$ . Hence $⟨ u_{i}, v_{i} ⟩ = σ_{i}^{- 1}$ and $⟨ u_{i}, v_{j} ⟩ = 0$ for all $i \neq j$ .

We show that $v_{1} - σ_{1}^{- 1} u_{1}$ can be decomposed as $v_{1} - σ_{1} u_{1} + (σ_{1} - σ_{1}^{- 1}) u_{1}$ such that $v_{1} - σ_{1} u_{1} \in V^{⊥}$ and $(σ_{1} - σ_{1}^{- 1}) u_{1} \in U^{⊥}$ .

The containment $(σ_{1} - σ_{1}^{- 1}) u_{1} \in U^{⊥}$ is immediate. To show $v_{1} - σ_{1} u_{1} \in V^{⊥}$ , we need that $⟨ v_{1} - σ_{1} u_{1}, v_{i} ⟩ = 0$ for all $i \in [k]$ . For $i \geq 2$ , this is true since $⟨ u_{i}, v_{j} ⟩ = 0$ and $⟨ v_{i}, v_{j} ⟩ = 0$ . For $i = 1$ , we have $⟨ v_{1} - σ_{1} u_{1}, v_{1} ⟩ = 0$ since $∥ v_{1} ∥ = 1$ and $⟨ u_{1}, v_{1} ⟩ = σ_{1}^{- 1}$ . Consequently, $T^{'} (v_{1} - σ_{1}^{- 1} u_{1}) = v_{1} - σ_{1} u_{1}$ .

We compute $∥ ∥ v_{1} - σ_{1}^{- 1} u_{1} ∥ ∥ = \sqrt{1 - σ_{1}^{- 2}} > 0$ , since $σ_{1} > 1$ , and $∥ v_{1} - σ_{1} u_{1} ∥ = \sqrt{σ_{1}^{2} - 1}$ . This verifies (26), and thus $∥ T^{'} ∥ \geq σ_{1} = ∥ T ∥$ . ∎

To prove the lemma, we define $J = (J, I)$ , $U = W_{J, 1}^{⊥} \oplus W_{J, 2}^{⊥}$ and $V = W$ and let $T : R^{n} \to V$ and $T^{'} : R^{n} \to V^{⊥}$ be as in creftypecap 3.9. By assumption, ${0} \neq π_{I} (W) \Rightarrow {0} \neq V$ and ${0} \neq π_{J} (W^{⊥}) = W_{J, 1}^{⊥} \Rightarrow {0} \neq U$ . Applying Lemma 3.7, $U, V$ satisfy the conditions of creftypecap 3.9 and $T = {L L S}_{J}^{W, 1}$ . In particular, $∥ T^{'} ∥ = ∥ T ∥$ . Using the fact that $U^{⊥} = W_{J, 1} \oplus W_{J, 2}$ and $V^{⊥} = W^{⊥}$ , we similarly get that $T^{'} = {L L S}_{¯ J}^{W^{⊥}, 1}$ , where $¯ J = (I, J)$ . By (21) we have, for any $t \in π_{R_{I}^{n}} (W)$ , that $T t = {L L S}_{J}^{W, 1} (t) = L_{I}^{W} (t_{I})$ . Thus $∥ T ∥ \geq ∥ L_{I}^{W} ∥ \geq 1$ .

To finish the proof of the lemma from the claim, we show that $∥ T ∥ \leq ∥ L_{I}^{W} ∥$ . By a symmetric argument we get $∥ T^{'} ∥ = ∥ L_{J}^{W^{⊥}} ∥$ .

If $x \in R_{J}^{n}$ , then $T x \in W \cap R_{J}^{n}$ because any $s \in W_{J, 2}^{⊥}, t \in π_{I} (W)$ with $s + t = 0$ must have $s = t = 0$ since $W_{J, 2}^{⊥}$ is orthogonal to $π_{I} (W)$ . But $W \cap R_{J}^{n}$ and $W_{J, 1}^{⊥}$ are orthogonal, so $∥ T x ∥ \leq ∥ x ∥$ because $x = T x + (x - T x)$ is an orthogonal decomposition.

If $y \in R_{I}^{n}$ , then $y_{J} = 0$ and hence $(T y)_{J} = (T y - y)_{J}$ . Since $(T y - y)_{J} \in W_{J, 1}^{⊥} = π_{J} (W \cap R_{J}^{n})^{⊥}$ , we see that $T y \in (W \cap R_{J}^{n})^{⊥}$ . As such, for any $x \in R_{J}^{n}, y \in R_{I}^{n}$ , we see that $x ⊥ y$ and $T x ⊥ T y$ . For $x, y \neq 0$ , we thus have that

\frac{∥ T (x + y) ∥^{2}}{∥ x + y ∥^{2}} = \frac{∥ T (x) ∥^{2} + ∥ T (y) ∥^{2}}{∥ x ∥^{2} + ∥ y^{2} ∥} \leq max {\frac{∥ T (x) ∥^{2}}{∥ x ∥^{2}}, \frac{∥ T (y) ∥^{2}}{∥ y ∥^{2}}} \leq max {1, \frac{∥ T (y) ∥^{2}}{∥ y ∥^{2}}} .

Since $∥ L_{I}^{W} ∥ \geq 1$ , we must have that $∥ T t ∥ / ∥ t ∥$ is maximized by some $t \in R_{I}^{n}$ . From $Ker (T) = U$ it is clear that $∥ T t ∥ / ∥ t ∥$ is maximized by some $t \in U^{⊥}$ . Now, $U^{⊥} \cap R_{I}^{n} = π_{R_{I}^{n}} (W)$ , so any $t$ maximizing $∥ T t ∥ / ∥ t ∥$ satisfies $T t = L_{I}^{W} (t_{I})$ . Therefore, $∥ L_{I}^{W} ∥ \geq ∥ T ∥$ . ∎

3.3.2 Partition lifting scores

A key insight is that if the layering $J$ is “well-separated”, then we indeed have $x Δ s^{l l} + s Δ x^{l l} \approx - x s$ , that is, the LLS direction is close to the affine scaling direction. This will be shown in Lemma 3.11. The notion of “well-separatedness” can be formalized as follows. Recall the definition of the lifting score (4). The lifting score of the layering $J = (J_{1}, J_{2}, \dots, J_{p})$ of $[n]$ with respect to $W$ is defined as

ℓ^{W} (J) := max 2 \leq k \leq p ℓ^{W} (J_{\geq k}) .

For $δ \in R_{+ +}^{n}$ , we use $ℓ^{W, δ} (I) := ℓ^{W Diag (δ)} (I)$ and $ℓ^{W, δ} (J) := ℓ^{W Diag (δ)} (J)$ . When the context is clear, we omit $W$ and write $ℓ^{δ} (I) := ℓ^{W, δ} (I)$ and $ℓ^{δ} (J) := ℓ^{W, δ} (J)$ .

The following important duality claim asserts that the lifting score of a layering equals the lifting score of the reverse layering in the orthogonal complement subspace. It is an immediate consequence of Proposition 3.8.

Lemma 3.10.

Let $W \subseteq R^{n}$ be a linear subspace, $δ \in R_{+ +}^{n}$ . For an ordered partition $J = (J_{1}, J_{2}, \dots, J_{p})$ , let $¯ J = (J_{p}, J_{p - 1}, \dots, J_{1})$ denote the reverse ordered partition. Then, we have

ℓ^{W, δ} (J) = ℓ^{W^{⊥}, δ^{- 1}} (¯ J) .

Proof.

Let $U = W d i a g (δ)$ . Note that $U^{⊥} = W^{⊥} d i a g (δ^{- 1})$ . Then by Proposition 3.8, for $2 \leq k \leq p$ , we have that

ℓ^{W, δ} (J_{\geq k}) = ℓ^{U} (J_{\geq k}) = ℓ^{U^{⊥}} (J_{\leq k - 1}) = ℓ^{U^{⊥}} ({¯ J}_{\geq p - k + 2}) = ℓ^{W^{⊥}, δ^{- 1}} ({¯ J}_{\geq p - k + 2}) .

In particular, $ℓ^{W, δ} (J) = ℓ^{W^{⊥}, δ^{- 1}} (¯ J)$ , as needed. ∎

The next lemma summarizes key properties of the LLS steps, assuming the partition has a small lifting score. The proof is deferred to Section 5.

Lemma 3.11.

Let $w = (x, y, s) \in N (β)$ for $β \in (0, 1 / 4]$ , let $μ = μ (w)$ and $δ = δ (w)$ . Let $J = (J_{1}, \dots, J_{p})$ be a layering with $ℓ^{δ} (J) \leq β / (32 n^{2})$ , and let $Δ w^{l l} = (Δ x^{l l}, Δ y^{l l}, Δ s^{l l})$ denote the LLS direction for the layering $J$ . Then the following properties hold.

We have

$∥ δ_{J_{k}} Δ x_{J_{k}}^{l l} + δ_{J_{k}}^{- 1} Δ s_{J_{k}}^{l l} + x_{J_{k}}^{1 / 2} s_{J_{k}}^{1 / 2} ∥$ $\leq 6 n ℓ^{δ} (J) \sqrt{μ}, \forall k \in [p], and$ (27)

$∥ δ Δ x^{l l} + δ^{- 1} Δ s^{l l} + x^{1 / 2} s^{1 / 2} ∥$ $\leq 6 n^{3 / 2} ℓ^{δ} (J) \sqrt{μ} .$ (28)
For the affine scaling direction $Δ w^{a} = (Δ x^{a}, Δ y^{a}, Δ s^{a})$ ,

$∥ R x^{l l} - R x^{a} ∥, ∥ R s^{l l} - R s^{a} ∥ \leq 6 n^{3 / 2} ℓ^{δ} (J) .$
For the residuals of the LLS steps we have $∥ R x^{l l} ∥, ∥ R s^{l l} ∥ \leq \sqrt{2 n}$ . For each $i \in [n]$ , $max {| R x_{i}^{l l} |, | R s_{i}^{l l} |} \geq \frac{1}{2} - \frac{3}{4} β$ .
Let $ε^{l l} (w) = {max}_{i \in [n]} min {| R x_{i}^{l l} |, | R s_{i}^{l l} |}$ , and define the step length as

$α$ $:= sup {α^{'} \in [0, 1] : \forall ¯ α \in [0, α^{'}] : w + ¯ α Δ w^{l l} \in N (2 β)} .$

We obtain the following bounds on the progress in the LLS step:

$μ (w + α Δ w^{l l})$ $= (1 - α) μ, and$

$α$ $\geq 1 - \frac{3 \sqrt{n} ε^{l l} (w)}{β} .$
We have $ε^{l l} (w) = 0$ if and only if $α = 1$ . These are further equivalent to $w + Δ w^{l l} = (x + Δ x^{l l}, y + Δ y^{l l}, s + Δ s^{l l})$ being an optimal solution to (LP).

3.4 The layering procedure

Our algorithm performs LLS steps on a layering with a low lifting score. A further requirement is that within each layer, the circuit imbalances $κ_{i j}^{δ}$ defined in (6) are suitably bounded. The rescaling here is with respect to $δ = δ (w)$ for the current iterate $w = (x, y, s)$ . To define the precise requirement on the layering, we first introduce an auxiliary graph. Throughout we use the parameter

γ := \frac{β}{2^{10} n^{5}} .

(29)

\setstretch

0.7^{inline,
backgroundcolor=black!30!white
, size=}^{inline,
backgroundcolor=black!30!white
, size=}todo: inline, backgroundcolor=black!30!white , size=Comment[BN1]:
We might not need the exponent $5$ anymore. I have to check.

The auxiliary graph

For a vector $δ \in R_{+ +}^{n}$ and $σ > 0$ , we define the directed graph $G_{δ, σ} = ([n], E_{δ, σ})$ such that $(i, j) \in E_{δ, σ}$ if $κ_{i j}^{δ} \geq σ$ . This is a subgraph of the circuit ratio digraph studied in Section 2, including only the edges where the circuit ratio is at least the threshold $σ$ . Note that we do not have direct access to this graph, as we cannot efficiently compute the values $κ_{i j}^{δ}$ .

At the beginning of the entire algorithm, we run the subroutine Find-Circuits( $A$ ) as in Theorem 2.19, where $W = Ker (A)$ . We assume the matroid $M (A)$ is non-separable. For a separable matroid, we can solve the subproblems of our LP on the components separately. Thus, for each $i \neq j$ , $i, j \in [n]$ , we obtain an estimate ${^κ}_{i j} \leq κ_{i j}$ . These estimates will be gradually improved throughout the algorithm.

Note that $κ_{i j}^{δ} = κ_{i j} δ_{j} / δ_{i}$ and ${^κ}_{i j}^{δ} = {^κ}_{i j} δ_{j} / δ_{i}$ . If ${^κ}_{i j}^{δ} \geq σ$ , then we are guaranteed $(i, j) \in E_{δ, σ}$ .

Definition 3.12.

Define ${^G}_{δ, σ} = ([n], {^E}_{δ, σ})$ to be the directed graph with edges $(i, j)$ such that ${^κ}_{i j}^{δ} \geq σ$ ; clearly, ${^G}_{δ, σ}$ is a subgraph of $G_{δ, σ}$ .

Lemma 3.13.

Let $δ \in R_{+ +}^{n}$ . For every $i \neq j$ , $i, j \in [n]$ , ${^κ}_{i j}^{δ} \cdot {^κ}_{j i}^{δ} \geq 1$ . Consequently, for any $0 < σ \leq 1$ , at least one of $(i, j) \in {^E}_{δ, σ}$ or $(j, i) \in {^E}_{δ, σ}$ .

Proof.

Recall the definition of ${^κ}_{i j}$ from Theorem 2.19. This is defined as the maximum of $| g_{j} / g_{i} |$ such that $g \in W$ , $s u p p (g) = C$ for some $C \in^C$ containing $i$ and $j$ . For the same vector $g$ , we get ${^κ}_{j i} \geq | g_{i} / g_{j} |$ . Consequently, ${^κ}_{i j} \cdot {^κ}_{j i} \geq 1$ , and also ${^κ}_{i j}^{δ} \cdot {^κ}_{j i}^{δ} \geq 1$ . The second claim follows by the assumption $σ \leq 1$ . ∎

Balanced layerings

We are ready to define the requirements on the layering in the algorithm. In the algorithm, $δ = δ (w)$ will correspond to the scaling of the current iterate $w = (x, y, s)$ .

Definition 3.14.

Let $δ \in R_{+ +}^{n}$ . The layering $J = (J_{1}, J_{2}, \dots, J_{p})$ of $[n]$ is $δ$ -balanced if

$ℓ^{δ} (J) \leq γ$ , and
$J_{k}$ is strongly connected in $G_{δ, γ / n}$ for all $k \in [p]$ .

The following lemma shows that within each layer, the $κ_{i j}^{δ}$ values are within a bounded range. This will play an important role in our potential analysis.

Lemma 3.15.

Let $0 < σ < 1$ and $t > 0$ , and $i, j \in [n]$ , $i \neq j$ .

If the graph $G_{δ, σ}$ contains a directed path of at most $t - 1$ edges from $j$ to $i$ , then

$κ_{i j}^{δ} < {(\frac{{¯ χ}^{*}}{σ})}^{t} .$
If $G_{δ, σ}$ contains a directed path of at most $t - 1$ edges from $i$ to $j$ , then

$κ_{i j}^{δ} > {(\frac{σ}{{¯ χ}^{*}})}^{t} .$

Proof.

For part a, let $j = i_{1}, i_{2}, \dots, i_{h} = i$ be a path in $G_{δ, σ}$ in $J$ from $j$ to $i$ with $h \leq t$ . That is, $κ_{i_{ℓ} i_{ℓ + 1}}^{δ} \geq σ$ for each $ℓ \in [h]$ . Theorem 2.13 yields

({¯ χ}^{*})^{t} \geq κ_{i j}^{δ} \cdot σ^{h - 1} > κ_{i j}^{δ} \cdot σ^{t},

since $h \leq t$ and $σ < 1$ . Part b follows using part a for $j$ and $i$ , and that $κ_{i j}^{δ} \cdot κ_{j i}^{δ} \geq 1$ according to Lemma 3.13. ∎

Description of the layering subroutine

Consider an iterate $w = (x, y, s) \in N (β)$ of the algorithm with $δ = δ (w)$ , The subroutine Layering $(δ,^κ)$ , described in Algorithm 1, constructs a $δ$ -balanced layering. We recall that the approximated auxilliary graph ${^G}_{δ, γ / n}$ with respect to $^κ$ is as in Definition 3.12

Input :

δ \in R_{+ +}^{n}

and

^κ \in R_{+ +}^{E}

Output :

δ

-balanced layering

J = (J_{1}, \dots, J_{p})

and updated values

^κ \in R_{+ +}^{E}

1 Compute the strongly connected components

C_{1}, C_{2}, \dots, C_{ℓ}

{^G}_{δ, γ / n}

, listed in the ordering imposed by

{^G}_{δ, γ / n}

;

¯ E \leftarrow {^E}_{δ, γ / n}

;

3 for $k = 2, \dots, ℓ$ do

4 Call Verify-Lift

(W Diag (δ), C_{\geq k}, γ)

that answers ‘pass’ or ‘fail’;

5 if the answer is ‘fail’ then

6 Let

i \in C_{\geq k}

j \in C_{< k}

, and

t

be the output of Verify-Lift such that

γ / n \leq t \leq κ_{i j}^{δ}

;

{^κ}_{i j} \leftarrow t δ_{i} / δ_{j}

;

¯ E \leftarrow ¯ E \cup {(i, j)}

;

11Compute strongly connected components

J_{1}, J_{2}, \dots, J_{p}

([n], ¯ E)

, listed in the ordering imposed by

{^G}_{δ, γ / n}

;

return $J = (J_{1}, J_{2}, \dots, J_{p}),^κ$ .

Algorithm 1 Layering(

δ,^κ

)

We now give an overview of the subroutine Layering $(δ,^κ)$ . We start by computing the strongly connected components (SCCs) of the directed graph ${^G}_{δ, γ / n}$ . The edges of this graph are obtained using the current estimates ${^κ}_{i j}^{δ}$ . According to Lemma 3.13, we have $(i, j) \in {^E}_{δ, γ / n}$ or $(j, i) \in {^E}_{δ, γ / n}$ for every $i, j \in [n]$ , $i \neq j$ . Hence, there is a linear ordering of the components $C_{1}, C_{2}, \dots, C_{ℓ}$ such that $(u, v) \in {^E}_{δ, γ / n}$ whenever $u \in C_{i}$ , $v \in C_{j}$ , and $i < j$ . We call this the ordering imposed by ${^G}_{δ, γ / n}$ .

Next, for each $k = 2, \dots, ℓ$ , we use the subroutine Verify-Lift $(W Diag (δ), C_{\geq k}, γ)$ described after Lemma 2.11. If the subroutine returns ‘pass’, then we conclude $ℓ^{δ} (C_{\geq k}) \leq γ$ , and proceed to the next layer. If the answer is ‘fail’, then the subroutine returns as certificates $i \in C_{\geq k}$ , $j \in C_{< k}$ , and $t$ such that $γ / n \leq t \leq κ_{i j}^{δ}$ . In this case, we update ${^κ}_{i j}^{δ}$ to the higher value $t$ . We add $(i, j)$ to an edge set $¯ E$ ; this edge set was initialized to contain ${^E}_{δ, γ / n}$ . After adding $(i, j)$ , all components $C_{ℓ}$ between those containing $i$ and $j$ will be merged into a single strongly connected component. To see this, recall that if $i^{'} \in C_{ℓ}$ and $j^{'} \in C_{ℓ^{'}}$ for $ℓ < ℓ^{'}$ , then $(i^{'}, j^{'}) \in {^E}_{δ, γ / n}$ according to Lemma 3.13.

Finally, we compute the strongly connected components of $([n], ¯ E)$ . We let $J_{1}, J_{2}, \dots, J_{p}$ denote their unique acyclic order, and return these layers.

Lemma 3.16.

The subroutine Layering $(δ,^κ)$ returns a $δ$ -balanced layering in $O (n m^{2} + n^{2})$ time.

The difficult part of the proof is showing the running time bound. We note that the weaker bound $O (n^{2} m^{2})$ can be obtained by a simpler argument.

Proof.

We first verify that the output layering is indeed $δ$ -balanced. For property a of Definition 3.14, note that each $J_{q}$ component is the union of some of the $C_{k}$ ’s. In particular, for every $q \in [p]$ , the set $J_{\geq q} = C_{\geq k}$ for some $k \in [ℓ]$ . Assume now $ℓ^{δ} (C_{\geq k}) > γ$ . At step $k$ of the main cycle, the subroutine Verify-Lift returned the answer ‘fail’, and a new edge $(i, j) \in E$ was added with $i \in C_{\geq k}$ , $j \in C_{< k}$ . Note that we already had $(j, i) \in {^E}_{δ, γ / n}$ , since $j \in C_{r}$ for some $r < k$ , and $i \in C_{r^{'}}$ for $r^{'} \geq k$ . This contradicts the choice of $J_{\geq q}$ as a maximal strongly connected component in $([n], E)$ .

Property b follows since all new edges added to $E$ have $κ_{i j} \geq γ / n$ . Therefore, $([n], E)$ is a subgraph of $G_{δ, γ / n}$ .

Let us now turn to the computational cost. The initial strongly-connected components can be obtained in time $O (n^{2})$ , and the same bound holds for the computation of the final components. (The latter can be also done in linear time, exploiting the special structure that the components $C_{i}$ have a complete linear ordering.)

The second computational bottleneck is the subroutine Verify-Lift. We assume a matrix $M \in R^{n \times (n - m)}$ is computed at the very beginning such that $r a n g e (M) = W$ . We first explain how to implement one call to Verify-Lift in $O (n (n - m)^{2})$ time. We then sketch how to amortize the work across the different calls to Verify-Lift, using the nested structure of the layering, to implement the whole procedure in $O (n (n - m)^{2})$ time. To turn this into $O (n m^{2})$ , we recall that the layering procedure is the same for $W$ and $W^{⊥}$ due to duality (Proposition 3.8). Since $dim (W^{⊥}) = m$ , applying this subroutine on $W^{⊥}$ instead of $W$ achieves the same result but in time $O (n m^{2})$ .

We now explain the implementation of Verify-Lift, where we are given as input $C \subseteq [n]$ and the basis matrix $M \in R^{n \times (n - m)}$ as above with $r a n g e (M) = W$ . Clearly, the running time is dominated by the computation of the set $I \subseteq C$ and the matrix $B \in R^{([n] ∖ C) \times | I |}$ satisfying $L_{C}^{W} (x)_{[n] ∖ C} = B x_{I}$ , for $x \in π_{C} (W)$ . We explain how to compute $I$ and $B$ from $M$ using column operations (note that these preserve the range). The valid choices for $I \subseteq C$ are in correspondence with maximal sets of linear independent rows of $MC,\vbox\scalebox{.5}{∙}$ , noting then that $| I | = r$ where $r:=rk(MC,\vbox\scalebox{.5}{∙})$ . Let $D_{1} = [n - m - r]$ and $D_{2} = [n - m] ∖ [n - m - r]$ . By applying columns operations to $M$ , we can compute $I \subseteq C$ such that $M_{I, D_{2}} = I_{r}$ ( $r \times r$ identity) and $M_{C, D_{1}} = 0$ . This requires $O (n (n - m) | C |)$ time using Gaussian elimination. At this point, note that $π_{C} (W) = r a n g e (M_{C, D_{2}})$ , $π_{I} (W) = R^{I}$ and $range(M\vbox\scalebox{.5}{∙},D1)=W∩Rn[n]∖C$ . To compute $B$ , we must transform the columns of $M\vbox\scalebox{.5}{∙},D2$ into minimum norm lifts of $e_{i} \in π_{I} (W)$ into $W$ , for all $i \in I$ . For this purpose, it suffices to make the columns of $M_{[n] ∖ C, D_{2}}$ orthogonal to the range of $M_{[n] ∖ C, D_{1}}$ . Applying Gram-Schmidt orthogonalization, this requires $O ((n - | C |) (n - m) (n - m - r))$ time. From here, the desired matrix $B = M_{[n] ∖ C, D_{2}}$ . Thus, the total running time of Verify-Lift is $O (n (n - m) | C | + (n - | C |) (n - m) (n - m - r)) = O (n (n - m)^{2})$ .

We now sketch how to amortize the work of all the calls of Verify-Lift during the layering algorithm, to achieve a total $O (n (n - m)^{2})$ running time. Let $C_{1}, \dots, C_{ℓ}$ denote the candidate SCC layering. Our task is to compute the matrices $B_{k}$ , $2 \leq k \leq ℓ$ , needed in the calls to Verify-Lift on $W, C_{\geq k}$ , $2 \leq k \leq ℓ$ , in total $O (n (n - m)^{2})$ time. We achieve this in three steps working with the basis matrix $M$ as above. Firstly, by applying column operations to $M$ , we compute sets $I_{k} \subseteq C_{k}$ and $D_{k} = [| I_{\leq k} |] ∖ [| I_{< k} |]$ , $k \in [ℓ]$ , such that $M_{I_{k}, D_{k}} = I_{r_{k}}$ , where $r_{k} = | I_{k} |$ , and $M_{C_{\geq k}, D_{< k}} = 0$ , $2 \leq k \leq ℓ$ . Note that this enforces $\sum_{k = 1}^{ℓ} r_{k} = (n - m)$ . This computation requires $O (n (n - m)^{2})$ time using Gaussian elimination. This computation achieves $r a n g e (M_{C_{k}, D_{k}}) = π_{C_{k}} (W \cap R_{C_{\leq k}}^{n})$ , $r a n g e (M_{C_{\geq k}, D_{\geq k}}) = π_{C_{\geq k}} (W)$ and $range(M\vbox\scalebox{.5}{∙},D≤k)=W∩RnC≤k$ , for all $k \in [ℓ]$ .

From here, we block orthogonalize $M$ , such that the columns of $M\vbox\scalebox{.5}{∙},Dk$ are orthogonal to the range of $M\vbox\scalebox{.5}{∙},D<k$ , $2 \leq k \leq ℓ$ . Applying an appropriately adapted Gram-Schmidt orthogonalization, this requires $O (n (n - m)^{2})$ time. Note that this operation maintains $M_{I_{k}, D_{k}} = I_{r_{k}}$ , $k \in [ℓ]$ , since $M_{C_{\geq k}, D_{< k}} = 0$ . At this point, for $k \in [ℓ]$ the columns of $M\vbox\scalebox{.5}{∙},Dk$ are in correspondence with minimum norm lifts of $e_{i} \in π_{D_{\geq k} (W)}$ into $W$ , for all $i \in I_{k}$ . Note that to compute the matrix $B_{k}$ we need the lifts of $e_{i} \in π_{D_{\geq k} (W)}$ , for all $i \in I_{\geq k}$ instead of just $i \in I_{k}$ .

We now compute the matrices $B_{ℓ}, \dots, B_{2}$ in this order via the following iterative procedure. Let $k$ denote the iteration counter, which decrements from $ℓ$ to $2$ . For $k = ℓ$ (first iteration), we let $B_{ℓ} = M_{C_{< ℓ}, D_{ℓ}}$ and decrement $k$ . For $k < ℓ$ , we eliminate the entries of $M_{I_{k}, D_{> k}}$ by using the columns of $M\vbox\scalebox{.5}{∙},Dk$ . We then let $B_{k} = M_{C_{< k}, D_{\geq k}}$ and decrement $k$ . To justify correctness, one need only notice that at the end of iteration $k$ , we maintain the orthogonality of $M\vbox\scalebox{.5}{∙},D≥k$ to the range of $M\vbox\scalebox{.5}{∙},D<k$ and that $M_{I_{\geq k}, D_{\geq k}} = I_{| I_{\geq k} |}$ is the appropriate identity. The cost of this procedure is the same as a full run of Gaussian elimination and thus is bounded by $O (n (n - m)^{2})$ . The calls to Verify-Lift during the layering procedure can thus be executed in $O (n (n - m)^{2}))$ amortized time as claimed. ∎

3.5 The overall algorithm

Input :

A \in R^{m \times n}

b \in R^{m}

c \in R^{n}

, and an initial feasible solution

w^{0} = (x^{0}, y^{0}, s^{0}) \in N (1 / 8)

to (LP).

Output : Optimal solution

w^{*} = (x^{*}, y^{*}, s^{*})

to (LP).

1 Call Find-Circuits

(A)

to obtain the lower bounds

{^κ}_{i j}

for each

i, j \in [n]

i \neq j

;

k \leftarrow 0, α \leftarrow 0

;

3 repeat

4 /* Predictor step */

5 Compute affine scaling direction

Δ w^{a} = (Δ x^{a}, Δ y^{a}, Δ s^{a})

for

w

;

6 if $ε^{a} (w) < 10 n^{3 / 2} γ$ then // Recall

ε^{a} (w)

defined in (20)

δ \leftarrow (s^{k})^{1 / 2} (x^{k})^{- 1 / 2}

;

(J,^κ) \leftarrow

Layering(

δ

^κ

);

9 Compute Layered Least Squares direction

Δ w^{l l} = (Δ x^{l l}, Δ y^{l l}, Δ s^{l l})

for the layering

J

and

w

;

Δ w \leftarrow Δ w^{l l}

;

12 else

Δ w \leftarrow Δ w^{a}

;

α \leftarrow sup {α^{'} \in [0, 1] : \forall ¯ α \in [0, α^{'}] : w + ¯ α Δ w \in N (1 / 4)}

;

w^{'} \leftarrow w^{k} + α Δ w

;

16 /* Corrector step */

17 Compute centrality direction

Δ w^{c} = (Δ x^{c}, Δ y^{c}, Δ s^{c})

for

w^{'}

;

w^{k + 1} \leftarrow w^{'} + Δ w^{c}

;

k \leftarrow k + 1

;

21until $μ (w^{k}) = 0$ ;

return $w^{k} = (x^{k}, y^{k}, s^{k})$ .

Algorithm 2 LP-Solve(

A, b, c, w^{0}

)

Algorithm 2 presents the overall algorithm LP-Solve $(A, b, c, w^{0})$ . We assume that an initial feasible solution $w^{0} = (x^{0}, y^{0}, s^{0}) \in N (β)$ is given. We address this in Section 7, by adapting the extended system used in [VY96]. We note that this subroutine requires an upper bound on ${¯ χ}^{*}$ . Since computing ${¯ χ}^{*}$ is hard, we can implement it by a doubling search on $log {¯ χ}^{*}$ , as explained in Section 7. Other than for initialization, the algorithm does not require an estimate on ${¯ χ}^{*}$ .

The algorithm starts with the subroutine Find-Circuits $(A)$ as in Theorem 2.19. The iterations are similar to the MTY Predictor-Corrector algorithm [MTY93]. The main difference is that certain affine scaling steps are replaced by LLS steps. In every predictor step, we compute the affine scaling direction, and consider the quantity $ε^{a} (w) = {max}_{i \in [n]} min {| R x_{i}^{a} |, | R s_{i}^{a} |}$ . If this is above the threshold $10 n^{3 / 2} γ$ , then we perform the affine scaling step. However, in case $ε^{a} (w) < 10 n^{3 / 2} γ$ , we use the LLS direction instead. In each such iteration, we call the subroutine Layering( $δ,^κ$ ) (Algorithm 1) to compute the layers, and we compute the LLS step for this layering.

Another important difference is that the algorithm does not require a final rounding step. It terminates with the exact optimal solution $w^{*}$ once a predictor step is able to perform a full step with $α = 1$ .

Theorem 3.17.

For given $A \in R^{m \times n}$ , $b \in R^{m}$ , $c \in R^{n}$ , and an initial feasible solution $w^{0} = (x^{0}, y^{0}, s^{0}) \in N (1 / 8)$ , Algorithm 2 finds an optimal solution to (LP) in $O (n^{2.5} log n log ({¯ χ}_{A}^{*} + n))$ iterations.

Remark 3.18.

Whereas using LLS steps enables us to give a strong bound on the total number of iterations, finding LLS directions has a significant computational overhead as compared to finding affine scaling directions. The layering $J$ can be computed in time $O (n m^{2})$ (Lemma 3.16), and the LLS steps also require $O (n m^{2})$ time, see [VY96, MMT98]. This is in contrast to the computational cost $O (n^{ω})$ of an affine scaling direction. Here $ω < 2.373$ is the matrix multiplication constant [VW12].

We now sketch a possible approach to amortize the computational cost of the LLS steps over the sequence of affine scaling steps. It was shown in [MT05] that for the MTY P-C algorithm, the “bad” scenario between two crossover events amounts to a series of affine scaling steps where the progress in $μ$ increases exponentially from every iteration to the next. This corresponds to the term $O (min {n^{2} log log (μ_{0} / η), log (μ_{0} / η)})$ in their running time analysis. Roughly speaking, such a sequence of affine scaling steps indicates that an LLS step is necessary.

Hence, we could observe these accelerating sequences of affine scaling steps, and perform an LLS step after we see a sequence of length $O (log n)$ . The progress made by these affine scaling steps offsets the cost of computing the LLS direction.

4 The potential function and the overall analysis

Let $μ > 0$ and $δ (μ) = s (μ)^{1 / 2} x (μ)^{- 1 / 2}$ correspond to the point on the central path. For $i, j \in [n]$ , $i \neq j$ , we define

ϱ^{μ} (i, j) := \frac{log κ_{i j}^{δ (μ)}}{log (3 n {¯ χ}_{A}^{*} / γ)},

and the main potentials in the algorithm as

Ψ^{μ} (i, j) := max {1, min {2 n, inf 0 < μ^{'} < μ ϱ^{μ^{'}} (i, j)}} and Ψ (μ) := \sum i, j \in [n], i \neq j {log}_{2} Ψ^{μ} (i, j) .

The quantity $Ψ^{μ} (i, j)$ is motivated by the bounds in Lemma 3.15. The next statement is an immediate consequence of this lemma and (16).

Lemma 4.1.

Let $w = (x, y, s) \in N (β)$ for $β \in (0, 1 / 4]$ , let $μ = μ (w)$ , and $δ = δ (w)$ . Let $i, j \in [n]$ , $i \neq j$ . If the graph $G_{δ, γ / (3 n)}$ contains a path from $j$ to $i$ of at most $t - 1$ edges, then $ϱ^{μ} (i, j) < t$ . If there is a path of at most $t - 1$ edges from $i$ to $j$ , then $- t < ϱ^{μ} (i, j)$ .

If $Ψ^{μ} (i, j) \geq t$ , then $i$ and $j$ cannot be together on a layer of size $\leq t$ , and $j$ cannot be on a layer preceding the layer containing $i$ in any $δ (w^{'})$ -balanced layering, where $w^{'} = (x^{'}, y^{'}, s^{'}) \in N (β)$ with $μ (w^{'}) < μ$ .

Our potentials $Ψ^{μ} (i, j)$ can be seen as fine-grained analogues of the crossover events analyzed in [VY96, MT03, MT05]. Roughly speaking, a crossover event corresponds to $Ψ^{μ} (i, j)$ increasing above $n$ , meaning that $i$ and $j$ cannot be contained in the same layer after the normalized duality gap decreases below $μ$ .

In what follows, we formulate four lemmas and use them to prove Theorem 3.17. For the lemmas, we only highlight some key ideas here, and defer the full proofs to Section 6.

For a solution $w \in N (β)$ , $Δ w^{l l}$ refers to the LLS direction found in the algorithm, and $R x^{l l}$ and $R s^{l l}$ denote the residuals as in (18). For a subset $I \subset [n]$ recall the definition

ε_{I}^{l l} (w) := max i \in I min {| R x_{i}^{l l} |, | R s_{i}^{l l} |} .

Another important quantity in the analysis is

ξ_{I}^{l l} (w) := min {∥ R x_{I}^{l l} ∥, ∥ R s_{I}^{l l} ∥}

for a subset $I \subset [n]$ . For a layering $J = (J_{1}, J_{2}, \dots, J_{p})$ , we let

ξ_{J}^{l l} (w) = max k \in [p] ξ_{J_{k}}^{l l} (w) .

The key idea of the analysis is to extract information about the optimal solution $w^{*} = (x^{*}, y^{*}, s^{*})$ from the LLS direction. The first main lemma shows that if $∥ R x_{J_{q}}^{l l} ∥$ is large on some layer $J_{q}$ , then for at least one index $i \in J_{q}$ , $x_{i}^{*} / x_{i} \geq 1 / p o l y (n)$ ; the analogous statement holds for $∥ R s_{J_{q}}^{l l} ∥$ .

Lemma 4.2.

Let $w = (x, y, s) \in N (β)$ for $β \in (0, 1 / 8]$ , and let $J = (J_{1}, \dots, J_{p})$ be a $δ (w)$ -balanced layering, and let $Δ w^{l l} = (Δ x^{l l}, Δ y^{l l}, Δ s^{l l})$ be the corresponding LLS direction. Then the following statement holds for every $q \in [p]$ :

There exists $i \in J_{q}$ such that

(30)
There exists $j \in J_{q}$ such that

$s_{j}^{*} \geq \frac{2 s_{j}}{3 \sqrt{n}} \cdot (∥ R s_{J_{q}}^{l l} ∥ - 2 γ n) .$ (31)

We outline the main idea of the proof of part a; part b follows analogously using the duality of the lifting scores (Lemma 3.10). On layer $q$ , the LLS step minimizes $∥ δ_{J_{q}} (x_{J_{q}} + Δ x_{J_{q}}) ∥$ , subject to $Δ x_{J_{> q}} = Δ x_{J_{> q}}^{l l}$ . By making use of the assumption $ℓ^{δ (w)} (J_{> q}) \leq γ$ , we can show the existence of a point $z \in W + x^{*}$ such that $∥ δ_{J_{q}} (z_{J_{q}} - x_{J_{q}}^{*}) ∥$ is small, and $z_{J_{> q}} = x_{J_{> q}} + Δ x_{J_{> q}}^{l l}$ . By the choice of $Δ x_{J_{q}}^{l l}$ , we have $∥ δ_{J_{q}} z_{J_{q}} ∥ \geq ∥ δ_{J_{q}} (x_{J_{q}} + Δ x_{J_{q}}) ∥ = \sqrt{μ} ∥ R x_{J_{q}}^{l l} ∥$ . Therefore, $∥ δ_{J_{q}} x_{J_{q}}^{*} / \sqrt{μ} ∥$ cannot be much smaller than $∥ R x_{J_{q}}^{l l} ∥$ . Noting that $δ_{J_{q}} x_{J_{q}}^{*} / \sqrt{μ} \approx x_{J_{q}}^{*} / x_{J_{q}}$ , we obtain a lower bound on $x_{i}^{*} / x_{i}$ for some $i \in J_{q}$ .

We emphasize that the lemma only shows the existence of such indices $i$ and $j$ , but does not provide an efficient algorithm for identifying them. It is also useful to note that for any $i \in [n]$ , $max {| R x_{i}^{l l} |, | R s_{i}^{l l} |} \geq \frac{1}{2} - \frac{5}{4} β$ according to Lemma 3.11 c. Thus, for each $q \in [p]$ , we obtain a positive lower bound either in case a or in case b.

The next lemma shows how we can argue for increase in the potential function value for multiple pairs of variables, if we have lower bounds on both $x_{i}^{*}$ and $s_{j}^{*}$ for some $i, j \in [n]$ , along with a lower bound on $ϱ^{μ} (i, j)$ .

Lemma 4.3.

Let $w = (x, y, s) \in N (2 β)$ for $β \in (0, 1 / 8]$ , let $μ = μ (w)$ and $δ = δ (w)$ . Let $i, j \in [n]$ and $2 \leq τ \leq n$ such that for the optimal solution $w^{*} = (x^{*}, y^{*}, s^{*})$ , we have $x_{i}^{*} \geq β x_{i} / (2^{10} n^{5.5})$ and $s_{j}^{*} \geq β s_{j} / (2^{10} n^{5.5})$ , and assume $ϱ^{μ} (i, j) \geq - τ$ . Let $μ^{'}$ be the normalized duality gap after $Ω (\sqrt{n} τ log ({¯ χ}^{*} + n))$ iterations subsequent to the iterate $w$ . Then $Ψ^{μ^{'}} (i, j) \geq 2 τ$ , and for every $ℓ \in [n] ∖ {i, j}$ , either $Ψ^{μ^{'}} (i, ℓ) \geq 2 τ$ , or $Ψ^{μ^{'}} (ℓ, j) \geq 2 τ$ .

We note that $i$ and $j$ as in the lemma are necessarily different, since $i = j$ would imply $0 = x_{i}^{*} s_{i}^{*} \geq β^{2} μ / (2^{20} n^{11})$ .

Let us illustrate the idea of the proof of $Ψ^{μ^{'}} (i, j) \geq 2 τ$ . For $i$ and $j$ as in the lemma, and for a central path element $w^{'} = w (μ^{'})$ for $μ^{'} < μ$ , we have $x_{i}^{'} \geq x_{i}^{*} / n \geq β x_{i} / (2^{10} n^{6.5})$ and $s_{j}^{'} \geq s_{j}^{*} / n \geq β s_{j} / (2^{10} n^{6.5})$ by the near-monotonicity of the central path (Lemma 3.3). Note that

κ_{i j}^{δ^{'}} = κ_{i j} \cdot \frac{δ_{j}^{'}}{δ_{i}^{'}} = κ_{i j} \cdot \frac{x_{i}^{'} s_{j}^{'}}{μ^{'}} \geq κ_{i j} \cdot \frac{β^{2} x_{i} s_{j}}{2^{20} n^{13} μ^{'}} \geq \frac{β^{2} (1 - β)^{2}}{2^{20} n^{13}} \cdot κ_{i j}^{δ} \cdot \frac{μ}{μ^{'}},

where the last inequality uses Corollary 3.2. Consequently, as $μ^{'}$ sufficiently decreases, $κ_{i j}^{δ^{'}}$ will become much larger than $κ_{i j}^{δ}$ . The claim on $ℓ \in [n] ∖ {i, j}$ can be shown by using the triangle inequality $κ_{i k} \cdot κ_{k j} \geq κ_{i j}$ shown in Lemma 2.20.

Assume now $ξ_{J_{q}}^{l l} (w) \geq 4 γ n$ for some $q \in [p]$ in the LLS step. Then, Lemma 4.2 guarantees the existence of $i, j \in J_{q}$ such that $x_{i}^{*} / x_{i}, s_{j}^{*} / s_{j} \geq \frac{4}{3 \sqrt{n}} γ > β / (2^{10} n^{5 .5})$ . Further, Lemma 4.1 gives $ϱ^{μ} (i, j) \geq - | J_{q} |$ . Hence, Lemma 4.3 is applicable for $i$ and $j$ with $τ = | J_{q} |$ .

The overall potential argument in the proof of Theorem 3.17 uses Lemma 4.3 in three cases: $ξ_{J}^{l l} (w) \geq 4 γ n$ (Lemma 4.2 is applicable as above); $ξ_{J}^{l l} (w) < 4 γ n$ and $ℓ^{δ^{+}} (J) \leq 3 γ n$ (Lemma 4.4); and $ξ_{J}^{l l} (w) < 4 γ n$ and $ℓ^{δ^{+}} (J) > 3 γ n$ (Lemma 4.5). Here, $δ^{+}$ refers to the value of $δ$ after the LLS step. Note that $δ^{+} > 0$ is well-defined, unless the algorithm terminated with an optimal solution.

To prove these lemmas, we need to study how the layers “move” during the LLS step. We let $B = {t \in [n] : | R s_{t}^{l l} | < 4 γ n}$ and $N = {t \in [n] : | R x_{t}^{l l} | < 4 γ n}$ . The assumption $ξ_{J}^{l l} (w) < 4 γ n$ means that for each layer $J_{k}$ , either $J_{k} \subseteq B$ or $J_{k} \subseteq N$ ; we accordingly refer to $B$ -layers and $N$ -layers.

Lemma 4.4.

Let $w = (x, y, s) \in N (β)$ for $β \in (0, 1 / 8]$ , and let $J = (J_{1}, \dots, J_{p})$ be a $δ (w)$ -balanced partition. Assume that $ξ_{J}^{l l} (w) < 4 γ n$ , and let $w^{+} = (x^{+}, y^{+}, s^{+}) \in N (2 β)$ be the next iterate obtained by the LLS step with $μ^{+} = μ (w^{+})$ and assume $μ^{+} > 0$ . Let $q \in [p]$ such that $ξ_{J}^{l l} (w) = ξ_{J_{q}}^{l l} (w)$ . If $ℓ^{δ^{+}} (J) \leq 3 γ n$ , then there exist $i, j \in J_{q}$ such that $x_{i}^{*} \geq β x_{i}^{+} / (16 n^{3 / 2})$ and $s_{j}^{*} \geq β s_{j}^{+} / (16 n^{3 / 2})$ . Further, for any $ℓ, ℓ^{'} \in J_{q}$ , we have $ϱ^{μ^{+}} (ℓ, ℓ^{'}) \geq - | J_{q} |$ .

For the proof sketch, without loss of generality, let $ξ_{J}^{l l} = ξ_{J_{q}}^{l l} = ∥ R x_{J_{q}}^{l l} ∥$ , that is, $J_{q}$ is an $N$ -layer. The case $ξ_{J_{q}}^{l l} = ∥ R s_{J_{q}}^{l l} ∥$ can be treated analogously. Since the residuals $∥ R x_{J_{q}}^{l l} ∥$ and $∥ R s_{J_{q}}^{l l} ∥$ cannot be both small, Lemma 4.2 readily provides a $j \in J_{q}$ such that $s_{j}^{*} / s_{j} \geq 1 / (6 \sqrt{n})$ . Using LABEL:lem:central_path_bounded_l1_norm, $s_{j}^{*} / s_{j}^{+} > (1 - β) / (6 (1 + 4 β) n^{3 / 2}) > β / (16 n^{3 / 2})$ .

The key ideas of showing the existence of an $i \in J_{q}$ such that $x_{i}^{*} \geq x_{i}^{+} / (16 n^{3 / 2})$ are the following. With $\approx$ , $⪅$ and $⪆$ , we write equalities and inequalities that hold up to constant and small polynomial factors. First, we show that (i) $∥ δ_{J_{q}} x_{J_{q}}^{+} ∥ ⪅ μ^{+} / \sqrt{μ}$ , and then, that (ii) $∥ δ_{J_{q}} x_{J_{q}}^{*} ∥ ⪆ μ^{+} / \sqrt{μ} .$

If we can show (i) and (ii) as above, we obtain that $∥ δ_{J_{q}} x_{J_{q}}^{*} ∥ ⪆ ∥ δ_{J_{q}} x_{J_{q}}^{+} ∥$ , and thus, $x_{i}^{*} ⪆ x_{i}^{+}$ for some $i \in J_{q}$ .

Let us now sketch the first step. By the assumption $J_{q} \subset N$ , one can show $x_{J_{q}}^{+} / x_{J_{q}} \approx μ^{+} / μ$ , and therefore

∥ δ_{J_{q}} x_{J_{q}}^{+} ∥ \approx \frac{μ^{+}}{μ} ∥ δ_{J_{q}} x_{J_{q}} ∥ \approx | J_{q} | \frac{μ^{+}}{μ} \sqrt{μ} ⪅ \frac{μ^{+}}{\sqrt{μ}} .

The second part of the proof, namely, lower bounding $∥ δ_{J_{q}} x_{J_{q}}^{*} ∥$ , is more difficult. We only show it now for the special case when $J_{q} = [n]$ . That is, we have a single layer only; in particular, the LLS step is the same as the affine scaling step $Δ x^{l l} = Δ x^{a}$ . The general case of multiple layers follows by making use of Lemma 3.11. In particular, for a sufficiently small $ℓ^{δ} (J)$ , the LLS step is close to the affine scaling step.

Hence, assume that $Δ x^{l l} = Δ x^{a}$ . Using the equivalent definition of the affine scaling step (17) as a minimum-norm point, we have $∥ δ x^{*} ∥ \geq ∥ δ (x + Δ x^{l l}) ∥ = \sqrt{μ} ∥ R x^{l l} ∥ = \sqrt{μ} ξ_{J}^{l l}$ . From Lemma 3.6, $μ^{+} / μ \leq \sqrt{n} ε^{a} (w) / β \leq \sqrt{n} ξ_{J}^{l l} / β$ . Thus, we see that $∥ δ x^{*} ∥ \geq β μ^{+} / (\sqrt{n μ})$ .

The final statement on lower bounding $ϱ^{μ^{+}} (ℓ, ℓ^{'}) \geq - | J_{q} |$ for any $ℓ, ℓ^{'} \in J_{q}$ follows by showing that $δ_{ℓ}^{+} / δ_{ℓ^{'}}^{+}$ remains close to $δ_{ℓ} / δ_{ℓ^{'}}$ , and hence the values of $κ^{μ^{+}} (ℓ, ℓ^{'})$ and $κ^{μ} (ℓ, ℓ^{'})$ are sufficiently close for indices on the same layer (Lemma 6.1).

Lemma 4.5.

Let $w = (x, y, s) \in N (β)$ for $β \in (0, 1 / 8]$ , and let $J = (J_{1}, \dots, J_{p})$ be a $δ (w)$ -balanced partition. Assume that $ξ_{J}^{l l} (w) < 4 γ n$ , and let $w^{+} = (x^{+}, y^{+}, s^{+}) \in N (2 β)$ be the next iterate obtained by the LLS step with $μ^{+} = μ (w^{+})$ and assume $μ^{+} > 0$ . If $ℓ^{δ^{+}} (J) > 3 γ n$ , then there exist two layers $J_{q}$ and $J_{r}$ , and $i \in J_{q}$ and $j \in J_{r}$ , $x_{i}^{*} \geq x_{i}^{+} / (8 n^{3 / 2})$ , and $s_{j}^{*} \geq s_{j}^{+} / (8 n^{3 / 2})$ . Further, $ϱ^{μ^{+}} (i, j) \geq - | J_{q} \cup J_{r} |$ , and for each $ℓ, ℓ^{'} \in J_{q} \cup J_{r}$ , $Ψ^{μ} (ℓ, ℓ^{'}) \leq | J_{q} \cup J_{r} |$ .

Consider now any $ℓ \in J_{k} \subseteq B$ . Then, since $R x_{ℓ}^{l l}$ is very close to 1, $x_{ℓ}^{+} \approx x_{ℓ}$ ; on the other hand $s_{ℓ}^{+}$ will “shoot down” close near the small value $R s_{ℓ}^{l l}$ . Conversely, for $ℓ \in J_{k} \subseteq N$ , $s_{ℓ}^{+} \approx s_{ℓ}$ , and $x_{ℓ}^{+}$ will “shoot down” to a small value.

The key step of the analysis is showing that the increase in $ℓ^{δ^{+}} (J)$ can be attributed to an $N$ -layer $J_{r}$ “crashing into” a $B$ -layer $J_{q}$ . That is, we show the existence of an edge $(i^{'}, j^{'}) \in E_{δ^{+}, γ / (3 n)}$ for $i^{'} \in J_{q}$ and $j^{'} \in J_{r}$ , where $r < q$ and $J_{q} \subseteq B$ , $J_{r} \subseteq N$ . This can be achieved by analyzing the matrix $B$ used in the subroutine Verify-Lift.

For the layers $J_{q}$ and $J_{r}$ , we can use Lemma 4.2 to show that there exists an $i \in J_{q}$ where $x_{i}^{*} / x_{i}$ is lower bounded, and there exists a $j \in J_{r}$ where $s_{j}^{*} / s_{j}$ is lower bounded. The lower bound on $ϱ^{μ^{+}} (i, j)$ and the upper bounds on the $Ψ^{μ} (ℓ, ℓ^{'})$ values can be shown by tracking the changes between the $κ^{δ} (ℓ, ℓ^{'})$ and $κ^{δ^{+}} (ℓ, ℓ^{'})$ values, and applying Lemma 4.1 both at $w$ and at $w^{+}$ .

Proof of Theorem 3.17.

We analyze the overall potential function $Ψ (μ)$ . By definition, $0 \leq Ψ (μ) \leq n (n - 1) ({log}_{2} n + 1)$ , and if $μ^{'} < μ$ then $Ψ (μ^{'}) \geq Ψ (μ)$ . By the iteration at $μ$ we mean the iteration where the normalized duality gap of the current iterate is $μ$ .

If $μ^{+} = 0$ at the end of an iteration, the algorithm terminates with an optimal solution. Recall from Lemma 3.11 e that this happens if and only if $ε^{l l} (w) = 0$ at a certain iteration.

From now on, assume that $μ^{+} > 0$ . We distinguish three cases at each iteration. These cases are well-defined even at iterations where affine scaling steps are used. At such iterations, $ξ_{J}^{l l} (w)$ still refers to the LLS residuals, even if these have not been computed by the algorithm. (Case I) $ξ_{J}^{l l} (w) \geq 4 γ n$ ; (Case II) $ξ_{J}^{l l} (w) \leq 4 γ n$ and $ℓ^{δ^{+}} (J) \leq 3 γ n$ ; and (Case III) $ξ_{J}^{l l} (w) \leq 4 γ n$ and $ℓ^{δ^{+}} (J) > 3 γ n$ .

Recall that the algorithm uses an LLS direction instead of the affine scaling direction whenever $ε^{a} (w) < 10 n^{3 / 2} γ$ . Consider now the case when an affine scaling direction is used, that is, $ε^{a} (w) \geq 10 n^{3 / 2} γ$ . According to Lemma 3.11 b, $∥ R x^{l l} - R x^{a} ∥, ∥ R s^{l l} - R s^{a} ∥ \leq 6 n^{3 / 2} γ$ . This implies that $ξ_{J}^{l l} (w) \geq 4 n^{3 / 2} γ \geq 4 n γ$ . Therefore, in cases II and III, an LLS step will be performed.

Starting with any given iteration, in each case we will identify a set $J \subseteq [n]$ of indices with $| J | > 1$ , and start a phase of $O (\sqrt{n} | J | log ({¯ χ}^{*} + n))$ iterations (that can be either affine scaling or LLS steps). In each phase, we will guarantee that $Ψ$ increases by at least $| J | - 1$ . As we can decompose the total sequence of iterations into disjoint phases, this yields the bound $O (n^{2.5} log n log ({¯ χ}^{*} + n))$ on the total number of iterations.

We now consider each of the cases. We always let $μ$ denote the normalized duality gap at the current iteration, and we let $q \in [p]$ be the layer such that $ξ_{J}^{l l} (w) = ξ_{J_{q}}^{l l} (w)$ .

Case I: $ξ_{J}^{l l} (w) \geq 4 γ n$ .

LABEL:lem:lower_bounds_for_crossover_events guarantees the existence of $x_{i}, s_{j} \in J_{q}$ such that $x_{i}^{*} / x_{i}, s_{i}^{*} / s_{i} \geq 4 γ n / (3 \sqrt{n}) > 1 / (2^{10} n^{5.5})$ . Further, according to Lemma 4.1, $ϱ^{μ} (i, j) \geq - | J_{q} |$ . Thus, Lemma 4.3 is applicable for $J = J_{q}$ . The phase starting at $μ$ comprises $O (\sqrt{n} | J_{q} | log ({¯ χ}^{*} + n))$ iterations, after which we get a normalized duality gap $μ^{'}$ such that $Ψ^{μ^{'}} (i, j) \geq 2 | J_{q} |$ , and for each $ℓ \in [n] ∖ {i, j}$ , either $Ψ^{μ^{'}} (i, ℓ) \geq 2 | J_{q} |$ , or $Ψ^{μ^{'}} (ℓ, j) \geq 2 | J_{q} |$ .

We can take advantage of these bounds for indices $ℓ \in J_{q}$ . Again by Lemma 4.1, for any $ℓ, ℓ^{'} \in J_{q}$ , we have $Ψ^{μ} (ℓ, ℓ^{'}) \leq ϱ^{μ} (ℓ, ℓ^{'}) \leq | J_{q} |$ . Thus, there are at least $| J_{q} | - 1$ pairs of indices $(ℓ, ℓ^{'})$ for which $Ψ^{μ} (ℓ, ℓ^{'})$ increases by at least $| J_{q} |$ between iterations at $μ$ and $μ^{'}$ .

We note that this analysis works regardless if an LLS step or an affine scaling step was performed in the iteration at $μ$ .

Case II: $ξ_{J}^{l l} (w) \leq 4 γ n$ and $ℓ^{δ^{+}} (J) \leq 3 γ n$ .

As explained above, in this case we perform an LLS step in the iteration at $μ$ , and we let $w^{+}$ denote the iterate obtained by the LLS step. For $J = J_{q}$ , Lemma 4.4 guarantees the existence of $i, j \in J_{q}$ such that $x_{i}^{*} / x_{i}^{+}, s_{j}^{*} / s_{j}^{+} > β / (16 n^{3 / 2})$ , and further, $ϱ^{μ^{+}} (i, j) > - | J_{q} |$ . We can therefore apply Lemma 4.3. The phase starting at $μ$ includes the LLS step leading to $μ^{+}$ (and the subsequent centering step), and the additional $O (\sqrt{n} | J_{q} | log ({¯ χ}^{*} + n))$ iterations as in Lemma 4.3. As in Case I, we get the desired potential increase compared to the potentials at $μ$ in layer $J_{q}$ .

Case III: $ξ_{J}^{l l} (w) \leq 4 γ n$ and $ℓ^{δ^{+}} (J) > 3 γ n$ .

Again, the iteration at $μ$ will use an LLS step. We apply Lemma 4.5, and set $J = J_{q} \cup J_{r}$ as in the lemma. The argument is the same as in Case II, using that LABEL:lem:case_layer_crashes explicitly states that $Ψ^{μ} (ℓ, ℓ^{'}) \leq | J |$ for any $ℓ, ℓ^{'} \in J$ . ∎

4.1 The iteration complexity bound for the Vavasis-Ye algorithm

We now show that the potential analysis described above also gives an improved bound $O (n^{2.5} log n$ $log ({¯ χ}_{A} + n))$ for the original VY algorithm [VY96].

We recall the VY layering step. Order the variables via $π$ such that $δ_{π (1)} \leq δ_{π (2)} \leq \dots \leq δ_{π (n)}$ . The layers will be consecutive sets in the ordering; a new layer starts with $π (i + 1)$ each time $δ_{π (i + 1)} > g δ_{π (i)}$ , for a parameter $g = p o l y (n) ¯ χ$ .

As outlined in the Introduction, the VY algorithm can be seen as a special implementation of our algorithm by setting ${^κ}_{i j} = g γ / n$ . With these edge weights, we have that ${^κ}_{i j}^{δ} \geq γ / n$ precisely if $g δ_{j} \geq δ_{i}$ .²²2For simplicity, in the Introduction we used $g x_{i} \geq x_{j}$ instead, which is almost the same in the proximity in the central path.

With these edge weights, it is easy to see that our Layering( $δ,^κ$ ) subroutine finds the exact same components as VY. Moreover, the layers will be the initial strongly connected components $C_{i}$ of $G_{δ, γ / n}$ : due to the choice of $g$ , this partition is automatically $δ$ -balanced. There is no need to call Verify-Lift.

The essential difference compared to our algorithm is that the values ${^κ}_{i j} = g γ / n$ are not lower bounds on $κ_{i j}$ as we require, but upper bounds instead. This is convenient to simplify the construction of the layering. On the negative side, the strongly connected components of ${^G}_{δ, γ / n}$ may not anymore be strongly connected in $G_{δ, γ / n}$ . Hence, we cannot use Lemma 4.1, and consequently, Lemma 4.3 does not hold.

Still, the ${^κ}_{i j}$ bounds are overestimating $κ_{i j}$ by at most a factor poly $(n) ¯ χ$ . Therefore, the strongly connected components of ${^G}_{δ, n / γ}$ are strongly connected in $G_{δ, σ}$ for some $σ = 1 / (p o l y (n) ¯ χ)$ .

Hence, the entire argument described in this section is applicable to the VY algorithm, with a different potential function defined with $¯ χ$ instead of ${¯ χ}^{*}$ . This is the reason why the iteration bound in Lemma 4.3, and therefore in Theorem 3.17, also changes to $¯ χ$ dependency.

It is worth noting that due to the overestimation of the $κ_{i j}$ values, the VY algorithm uses a coarser layering than our algorithm. Our algorithm splits up the VY layers into smaller parts so that $ℓ^{δ} (J)$ remains small, but within each part, the gaps between the variables are bounded as a function of ${¯ χ}_{A}^{*}$ instead of ${¯ χ}_{A}$ .

5 Properties of the layered least square step

We now prove Lemma 3.11, showing that for a layering with small enough $ℓ^{δ} (J)$ , the LLS step approximately satisfies (13), that is, $δ Δ x^{l l} + δ^{- 1} Δ s^{l l} \approx - x^{1 / 2} s^{1 / 2}$ . This also enables us to derive bounds on the norm of the residuals and on the step-length. We start by proving a few auxiliary technical claims. The next simple lemma allows us to take advantage of low lifting scores in the layering.

Lemma 5.1.

Let $u, v \in R^{n}$ be two vectors such that $u - v \in W$ . Let $I \subseteq [n]$ , and $δ \in R_{+ +}^{n}$ . Then there exists a vector $u^{'} \in W$ such that $u^{'} - u \in W$ , $u_{I}^{'} = v_{I}$ , and

∥ δ_{[n] ∖ I} (u_{[n] ∖ I}^{'} - u_{[n] ∖ I}) ∥ \leq ℓ^{δ} (I) ∥ δ_{I} (u_{I} - v_{I}) ∥ .

Proof.

We let

u^{'} := u + δ^{- 1} L_{I}^{δ} (δ_{I} (v_{I} - u_{I})) .

The claim follows by the definition of the lifting score $ℓ^{δ} (I)$ . ∎

The next lemma will be the key tool to prove Lemma 3.11. It is helpful to recall the characterization of the LLS step in Section 3.3.1.

Lemma 5.2.

Let $w = (x, y, s) \in N (β)$ for $β \in (0, 1 / 4]$ , let $μ = μ (w)$ and $δ = δ (w)$ . Let $J = (J_{1}, \dots, J_{p})$ be a layering, and let $Δ w^{l l} = (Δ x^{l l}, Δ y^{l l}, Δ s^{l l})$ denote the corresponding LLS direction. Let $Δ x \in ⨁_{k = 1}^{p} W_{J, k}$ and $Δ s \in ⨁_{k = 1}^{p} W_{J, k}^{⊥}$ as in (24) and (25), that is

	$δ Δ x^{l l} + δ^{- 1} Δ s + x^{1 / 2} s^{1 / 2} = 0,$		(32)
	$δ Δ x + δ^{- 1} Δ s^{l l} + x^{1 / 2} s^{1 / 2} = 0.$		(33)

Then, there exist vectors $Δ ¯ x \in ⨁_{k = 1}^{p} W_{J, k}$ and $Δ ¯ s \in ⨁_{k = 1}^{p} W_{J, k}^{⊥}$ such that

	$∥ δ_{J_{k}} (Δ {¯ x}_{J_{k}} - Δ x_{J_{k}}^{l l}) ∥$	$\leq 2 n ℓ^{δ} (J) \sqrt{μ} \forall k \in [p] and$		(34)
	$∥ δ_{J_{k}}^{- 1} (Δ {¯ s}_{J_{k}} - Δ s_{J_{k}}^{l l}) ∥$	$\leq 2 n ℓ^{δ} (J) \sqrt{μ} \forall k \in [p] .$		(35)

Proof.

Throughout, we use the shorthand notation $λ = ℓ^{δ} (J)$ . We construct $Δ ¯ x$ ; one can obtain $Δ ¯ s$ , using that the reverse layering has lifting score $λ$ in $W^{⊥} Diag (δ^{- 1})$ according to Lemma 3.10.

We proceed by induction, constructing $Δ {¯ x}_{J_{k}} \in W_{J, k}$ for $k = p, p - 1, \dots, 1$ . This will be given as $Δ {¯ x}_{J_{k}} = Δ x_{J_{k}}^{(k)}$ for a vector $Δ x^{(k)} \in W$ such that $Δ x_{J_{> k}}^{(k)} = 0$ . We prove the inductive hypothesis

∥ ∥ δ_{J_{\leq k}} (Δ x_{J_{\leq k}}^{(k)} - Δ x_{J_{\leq k}}^{l l}) ∥ ∥ \leq 2 λ \sqrt{μ} p \sum q = k + 1 \sqrt{| J_{q} |} .

(36)

Note that (34) follows by restricting the norm on the LHS to $J_{k}$ and since the sum on the RHS is $\leq n$ .

For $k = p$ , the RHS is 0. We simply set $Δ x^{(p)} = Δ x^{l l}$ , that is, $Δ {¯ x}_{J_{p}} = Δ x_{J_{p}}^{l l}$ , trivially satisfying the hypothesis. Consider now $k < p$ , and assume that we have a $Δ {¯ x}_{J_{k + 1}} = Δ x_{J_{k + 1}}^{(k + 1)}$ satisfying (36) for $k + 1$ . From (32) and the induction hypothesis, we get that

		$∥ δ_{J_{k + 1}} Δ {¯ x}_{J_{k + 1}} + δ_{J_{k + 1}}^{- 1} Δ s_{J_{k + 1}} ∥ \leq ∥ x_{J_{k + 1}}^{1 / 2} s_{J_{k + 1}}^{1 / 2} ∥ + ∥ δ_{J_{k + 1}} (Δ {¯ x}_{J_{k + 1}} - Δ x_{J_{k + 1}}^{l l}) ∥$
		$\leq ∥ x_{J_{k + 1}}^{1 / 2} s_{J_{k + 1}}^{1 / 2} ∥ + 2 λ \sqrt{μ} p \sum q = k + 2 \sqrt{\| J_{q} \|} \leq \frac{\sqrt{μ \| J_{k + 1} \|}}{1 + 2 β} + 2 n λ \sqrt{μ} < 2 \sqrt{μ \| J_{k + 1} \|},$

using also that $w \in N (β)$ , Proposition 3.1, and the assumptions $β \leq 1 / 4$ , $λ \leq β / (32 n^{2})$ . Note that $Δ {¯ x}_{J_{k + 1}} \in W_{J, k}$ and $Δ s_{J_{k + 1}} \in W_{J, k}^{⊥}$ are orthogonal vectors. The above inequality therefore implies

∥ δ_{J_{k + 1}} Δ {¯ x}_{J_{k + 1}} ∥ \leq 2 \sqrt{μ | J_{k + 1} |} .

Let us now use Lemma 5.1 to obtain $Δ x^{(k)}$ for $u = Δ x^{(k + 1)}$ , $v = 0$ , and $I = J_{> k}$ . That is, we get $Δ x_{J_{> k}}^{(k)} = 0$ , $Δ x^{(k)} \in W$ , and

	$∥ δ_{J_{\leq k}} (Δ x_{J_{\leq k}}^{(k)} - Δ x_{J_{\leq k}}^{(k + 1)}) ∥$	$\leq λ ∥ δ_{J_{> k}} Δ x_{J_{> k}}^{(k + 1)} ∥$
		$= λ ∥ δ_{J_{k + 1}} Δ {¯ x}_{J_{k + 1}} ∥ \leq 2 λ \sqrt{μ \| J_{k + 1} \|} .$

Together with the induction hypothesis (36) for $k + 1$ , we obtain the induction hypothesis for $k$ .

∎

Proof of Lemma 3.11.

Again, we use $λ = ℓ^{δ} (J)$ .

Part a. Clearly, (27) implies (28). To show (27), we use Lemma 5.2 to obtain $Δ ¯ x$ and $Δ ¯ s$ as in (34) and (35). We will also use $Δ x \in ⨁_{k = 1}^{p} W_{J, k}$ and $Δ s \in ⨁_{k = 1}^{p} W_{J, k}^{⊥}$ as in (32) and (33).

Select any layer $k \in [p]$ . From (32), we get that

∥ δ_{J_{k}} Δ {¯ x}_{J_{k}} + δ_{J_{k}}^{- 1} Δ s_{J_{k}} + x_{J_{k}}^{1 / 2} s_{J_{k}}^{1 / 2} ∥ = ∥ δ_{J_{k}} (Δ {¯ x}_{J_{k}} - Δ x_{J_{k}}^{l l}) ∥ \leq 2 n λ \sqrt{μ} .

(37)

Similarly, from (33), we see that

∥ δ_{J_{k}}^{- 1} Δ {¯ s}_{J_{k}} + δ_{J_{k}} Δ x_{J_{k}} + x_{J_{k}}^{1 / 2} s_{J_{k}}^{1 / 2} ∥ = ∥ δ_{J_{k}}^{- 1} (Δ {¯ s}_{J_{k}} - Δ s_{J_{k}}^{l l}) ∥ \leq 2 n λ \sqrt{μ} .

From the above inequalities, we see that

∥ δ_{J_{k}} (Δ {¯ x}_{J_{k}} - Δ x_{J_{k}}) + δ_{J_{k}}^{- 1} (Δ s_{J_{k}} - Δ {¯ s}_{J_{k}}) ∥ \leq 4 n λ \sqrt{μ} .

Since $δ_{J_{k}} (Δ {¯ x}_{J_{k}} - Δ x_{J_{k}})$ and $δ_{J_{k}}^{- 1} (Δ s_{J_{k}} - Δ {¯ s}_{J_{k}})$ are orthogonal vectors, we have

∥ δ_{J_{k}} (Δ {¯ x}_{J_{k}} - Δ x_{J_{k}}) ∥, ∥ δ_{J_{k}}^{- 1} (Δ s_{J_{k}} - Δ {¯ s}_{J_{k}}) ∥ \leq 4 n λ \sqrt{μ} .

Together with (34), this yields $∥ δ_{J_{k}} (Δ x_{J_{k}}^{l l} - Δ x_{J_{k}}) ∥ \leq 6 n λ \sqrt{μ}$ . Combined with (25), we get

∥ δ_{J_{k}} Δ x_{J_{k}}^{l l} + δ_{J_{k}}^{- 1} Δ s_{J_{k}}^{l l} + x_{J_{k}}^{1 / 2} s_{J_{k}}^{1 / 2} ∥ = ∥ δ_{J_{k}} (Δ x_{J_{k}}^{l l} - Δ x_{J_{k}}) ∥ \leq 6 n λ \sqrt{μ},

thus, (27) follows.

Part b.

Recall from Lemma 3.5 a that $\sqrt{μ} R x^{a} + \sqrt{μ} R s^{a} = x^{1 / 2} s^{1 / 2}$ . From part a, we can similarly see that

∥ \sqrt{μ} R x^{l l} + \sqrt{μ} R s^{l l} - x^{1 / 2} s^{1 / 2} ∥ \leq 6 n^{3 / 2} λ \sqrt{μ} .

From these, we get

∥ (R x^{l l} - R x^{a}) + (R s^{l l} - R s^{a}) ∥ \leq 6 n^{3 / 2} λ .

The claim follows since $R x^{l l} - R x^{a} \in W Diag (δ)$ and $R s^{l l} - R s^{a} \in W^{⊥} Diag (δ^{- 1})$ are orthogonal vectors.

Part c.

Both bounds follow from the previous part and Lemma 3.5 c, using the assumption $ℓ^{δ} (J) \leq β / (32 n^{2})$ .

Part d.

Let $w^{+} = w + α Δ w^{l l}$ . We need to find the largest value $α > 0$ such that $w^{+} \in N (2 β)$ . To begin, we first show that normalized duality gap $μ (w^{+}) = (1 - α) μ$ for any $α \in R$ . For this purpose, we use the decomposition:

(x + α Δ x^{l l}) (s + α Δ s^{l l}) = (1 - α) x s + α (x + Δ x^{l l}) (s + Δ s^{l l}) - α (1 - α) Δ x^{l l} Δ s^{l l} .

(38)

Recall from Part a that there exists $Δ x \in ⨁_{k = 1}^{p} W_{J, k}$ and $Δ s \in ⨁_{k = 1}^{p} W_{J, k}^{⊥}$ as in (32) and (33) such that $δ Δ x^{l l} + δ^{- 1} Δ s = - δ x$ and $δ Δ x + δ^{- 1} Δ s^{l l} = - δ^{- 1} s$ . In particular, $x + Δ x^{l l} = δ^{- 2} Δ s$ and $s + Δ s^{l l} = δ^{2} Δ x$ . Noting that $Δ x^{l l} ⊥ Δ s^{l l}$ and $Δ x ⊥ Δ s$ , taking the average of the coordinates on both sides of (38), we get that

$μ (w + α Δ w^{l l})$	$= (1 - α) μ (w) + α ⟨ x + Δ x^{l l}, s + Δ s^{l l} ⟩ / n - α (1 - α) ⟨ Δ x^{l l}, Δ s^{l l} ⟩ / n$
	$= (1 - α) μ (w) + α ⟨ δ^{- 2} Δ s, δ^{2} Δ x ⟩ / n$
	$= (1 - α) μ (w),$	(39)

as needed.

Let $ε := ε^{l l} (w)$ . To obtain the desired lower bound on the step-length, given (39) it suffices to show that for all $0 \leq α < 1 - \frac{3 \sqrt{n} ε}{β}$ that

∥ ∥ ∥ \frac{(x + α Δ x^{l l}) (s + α Δ s^{l l})}{} (1 - α) μ - e ∥ ∥ ∥ \leq 2 β .

(40)

We will need a bound on the product of the LLS residuals:

	$∥ ∥ ∥ R x^{l l} R s^{l l} - \frac{1}{μ} Δ x^{l l} Δ s^{l l} ∥ ∥ ∥$	$= ∥ ∥ ∥ \frac{x^{1 / 2} s^{1 / 2}}{\sqrt{μ}} \cdot \frac{δ Δ x^{l l} + δ^{- 1} Δ s^{l l} + x^{1 / 2} s^{1 / 2}}{\sqrt{μ}} ∥ ∥ ∥$		(41)
		$\leq 6 (1 + 2 β) n^{3 / 2} λ \leq \frac{β}{4},$		(41)

using Proposition 3.1, part a, and the assumptions $λ \leq β / (32 n^{2})$ , $β \leq 1 / 4$ . Another useful bound will be

	$∥ R x^{l l} R s^{l l} ∥^{2}$	$= \sum i \in [n] {∣ ∣ R x_{i}^{l l} ∣ ∣}^{2} {∣ ∣ R s_{i}^{l l} ∣ ∣}^{2} \leq ε^{2} \sum i \in [n] max {{∣ ∣ R x_{i}^{l l} ∣ ∣}^{2}, {∣ ∣ R s_{i}^{l l} ∣ ∣}^{2}}$		(42)
		$\leq ε^{2} (∥ R x^{l l} ∥^{2} + ∥ R s^{l l} ∥^{2}) \leq 2 n ε^{2} .$		(42)

The last inequality uses part b. We are ready to get a bound as in (40).

	$∥ ∥ \frac{(x + α Δ x^{l l}) (s + α Δ s^{l l})}{(1 - α) μ} - e ∥ ∥$	$\leq β + ∥ ∥ \frac{α^{2}}{(1 - α) μ} (x + Δ x^{l l}) (s + Δ s^{l l}) + \frac{α}{μ} (x s + x Δ s^{l l} + s Δ x^{l l}) ∥ ∥$
		$\leq β + \frac{α^{2}}{1 - α} ∥ R x^{l l} R s^{l l} ∥ + α ∥ ∥ ∥ R x^{l l} R s^{l l} - \frac{1}{μ} Δ x^{l l} Δ s^{l l} ∥ ∥ ∥$
		$\leq β + \frac{\sqrt{2 n} ε}{1 - α} + \frac{β}{4} \leq \frac{5}{4} β + \frac{\sqrt{2 n} ε}{1 - α} .$

This value is $\leq 2 β$ whenever $2 \sqrt{n} ε / (1 - α) \leq (3 / 4) β \Leftarrow α < 1 - \frac{3 \sqrt{n} ε}{β}$ , as needed.

Part e.

From part d, it is immediate that $ε^{l l} (w) = 0$ implies $α = 1$ . If $α = 1$ , we have that $w + Δ w^{l l}$ is the limit of (strictly) feasible solutions to (LP) and thus is also a feasible solution. Optimality of $w + Δ w^{l l}$ now follows from Part d, since $α = 1$ implies $μ (w + Δ w^{l l}) = 0$ . The remaining implication is that if $w + Δ w^{l l}$ is optimal, then $ε^{l l} (w) = 0$ . Recall that $R x_{i}^{l l} = δ_{i} (x_{i} + Δ x_{i}^{l l}) / \sqrt{μ}$ and $R s_{i}^{l l} = δ_{i}^{- 1} (s_{i} + Δ s_{i}^{l l}) / \sqrt{μ}$ . The optimality of $w + Δ w^{l l}$ means that for each $i \in [n]$ , either $x_{i} + Δ x_{i}^{l l} = 0$ or $s_{i} + Δ s_{i}^{l l} = 0$ . Therefore, $ε^{l l} (w) = 0$ . ∎

6 Proof of the main lemmas for the potential analysis

Proof of Lemma 4.2.

We prove part (i); part (ii) follows analogously using Lemma 3.10. Let $z \in W + d$ be the vector obtained from Lemma 5.1, for $u = x^{*}$ , $v = x + Δ x^{l l}$ , and $I = J_{> q}$ such that $z_{J_{> q}} = x_{J_{> q}} + Δ x_{J_{> q}}^{l l}$ and

∥ ∥ δ_{J_{\leq q}} (x_{J_{\leq q}}^{*} - z_{J_{\leq q}}) ∥ ∥ \leq γ ∥ ∥ δ_{J_{> q}} (x_{J_{> q}}^{*} - (x_{J_{> q}} + Δ x_{J_{> q}}^{l l})) ∥ ∥

Restricting to the components in $J_{q}$ , and dividing by $\sqrt{μ}$ , we get

∥ ∥ ∥ ∥ \frac{δ_{J_{q}} (x_{J_{q}}^{*} - z_{J_{q}})}{\sqrt{μ}} ∥ ∥ ∥ ∥ \leq γ ∥ ∥ ∥ ∥ \frac{δ_{J_{> q}} (x_{J_{> q}}^{*} - (x_{J_{> q}} + Δ x_{J_{> q}}^{l l}))}{\sqrt{μ}} ∥ ∥ ∥ ∥ \leq γ ∥ ∥ ∥ ∥ \frac{δ_{J_{> q}} x_{J_{> q}}^{*}}{\sqrt{μ}} ∥ ∥ ∥ ∥ + γ ∥ R x_{J_{> q}}^{l l} ∥ .

(43)

Since $w \in N (β)$ , from Proposition 3.1 and (16) we see that

\frac{δ_{i}}{\sqrt{μ}} \leq \frac{1}{\sqrt{1 - 2 β}} \cdot \frac{δ_{i} (w (μ))}{\sqrt{μ}} = \frac{1}{\sqrt{1 - 2 β}} \cdot \frac{1}{x_{i} (μ)},

and therefore

∥ ∥ ∥ ∥ \frac{δ_{J_{> q}} x_{J_{> q}}^{*}}{\sqrt{μ}} ∥ ∥ ∥ ∥ \leq \frac{1}{\sqrt{1 - 2 β}} ∥ ∥ x (μ)_{J_{> q}}^{- 1} x_{J_{> q}}^{*} ∥ ∥ \leq \frac{}{1} \sqrt{1 - 2 β} \cdot {∥ ∥ x (μ)_{J_{> q}}^{- 1} x_{J_{> q}}^{*} ∥ ∥}_{1} \leq \frac{n}{\sqrt{1 - 2 β}},

where the last inequality follows by Lemma 3.3.

Using the above bounds with (43), along with $∥ R x_{J_{\geq q}}^{l l} ∥ \leq ∥ R x^{l l} ∥ \leq \sqrt{2 n}$ from Lemma 3.11 c, we get

∥ ∥ ∥ \frac{δ_{J_{q}} z_{J_{q}}}{\sqrt{μ}} ∥ ∥ ∥ \leq ∥ ∥ ∥ ∥ \frac{δ_{J_{q}} x_{J_{q}}^{*}}{\sqrt{μ}} ∥ ∥ ∥ ∥ + \frac{γ n}{\sqrt{1 - 2 β}} + γ \sqrt{2 n} \leq ∥ ∥ ∥ ∥ \frac{δ_{J_{q}} x_{J_{q}}^{*}}{\sqrt{μ}} ∥ ∥ ∥ ∥ + 2 γ n,

using that $β \leq 1 / 8$ and $n \geq 3$ . Note that $z - x$ is a feasible solution to the least-squared problem optimally solved for layer $J_{q}$ by $x_{J_{q}}^{l l}$ , that is,

∥ R x_{J_{q}}^{l l} ∥ \leq ∥ ∥ ∥ \frac{δ_{J_{q}} z_{J_{q}}}{\sqrt{μ}} ∥ ∥ ∥ .

It follows that

∥ ∥ ∥ ∥ \frac{δ_{J_{q}} x_{J_{q}}^{*}}{\sqrt{μ}} ∥ ∥ ∥ ∥ \geq ∥ R x_{J_{q}}^{l l} ∥ - 2 γ n .

Let us pick $i = {a r g m a x}_{t \in J_{q}} | δ_{t} x_{t}^{*} |$ . Using Corollary 3.2,

\frac{x_{i}^{*}}{x_{i}} \geq \frac{1}{1 + 2 β} \cdot \frac{δ_{i} x_{i}^{*}}{\sqrt{μ}} \geq \frac{∥ R x_{J_{q}}^{l l} ∥ - 2 γ n}{(1 + 2 β) \sqrt{n}} \geq \frac{2}{3 \sqrt{n}} \cdot (∥ R x_{J_{q}}^{l l} ∥ - 2 γ n),

completing the proof. ∎

Proof of Lemma 4.3.

Let us select a value $μ^{'}$ such that

log μ - log μ^{'} \geq 5 τ log (\frac{3 n {¯ χ}_{A}^{*}}{γ}) + 29 log n + 44 - 4 log β .

We claim that the normalized duality gap decreases to such value within $O (\sqrt{n} τ \cdot log (n {¯ χ}^{*}))$ iterations. The step-lengths for the affine scaling and LLS steps are stated in Proposition 3.4 and Lemma 3.11 d.Whenever the algorithm chooses an LLS step, $ε^{a} (w) < 10 n^{3 / 2} γ$ . Thus, the progress in $μ$ will be at least as much (in fact, much better) than the $(1 - β / \sqrt{n})$ guarantee we use for the affine scaling step in Proposition 3.4.

Let $w^{'} = (x^{'}, y^{'}, s^{'})$ be the central path element corresponding to $μ^{'}$ , and let $δ^{'} = δ (w^{'})$ . From now on we use the shorthand notation

Θ := log (\frac{3 n {¯ χ}_{A}^{*}}{γ}) .

We first show that $Θ ϱ^{μ^{'}} (i, j) \geq 4 Θ τ + 16 log n + 22 log 2 - 2 log β$ for all such $μ^{'}$ , and therefore, $Θ Ψ^{μ^{'}} (i, j) \geq min (2 Θ n, 4 Θ τ + 16 log n + 22 log 2 - 2 log β) \geq 2 Θ τ$ by choice of $τ \leq n$ . According to Corollary 3.2, and recalling the definition $κ_{i j}^{δ} = κ_{i j} δ_{j} / δ_{i}$ , we see that

κ_{i j}^{δ} \leq \frac{κ_{i j}}{(1 - β)^{2}} \cdot \frac{x_{i} s_{j}}{μ}, and κ_{i j}^{δ^{'}} = κ_{i j} \cdot \frac{x_{i}^{'} s_{j}^{'}}{μ^{'}} .

Thus,

	$Θ ϱ^{μ^{'}} (i, j)$	$\geq Θ ϱ^{μ} (i, j) + log μ - log μ^{'} + 2 log (1 - β) + log x_{i}^{'} - log x_{i} + log s_{j}^{'} - log s_{j}$
		$\geq Θ ϱ^{μ} (i, j) + 5 Θ τ + 29 log n + 44 - 4 log β + 2 log (1 - β) + log x_{i}^{'} - log x_{i} + log s_{j}^{'} - log s_{j} .$

Using the near-monotonicity of the central path (LABEL:lem:central_path_bounded_l1_norm), we have $x_{i}^{'} \geq x_{i}^{*} / n$ and $s_{j}^{'} \geq s_{j}^{*} / n$ . Together with our assumptions $x_{i}^{*} \geq β x_{i} / (2^{10} n^{5.5})$ and $s_{i}^{*} \geq β x_{i} / (2^{10} n^{5.5})$ , we see that

log x_{i}^{'} - log x_{i} + log s_{j}^{'} - log s_{j} \geq - 13 log n - 20 log 2 + 2 log β .

Using the assumption $ϱ^{μ} (i, j) > - τ$ of the lemma, we see that $Θ ϱ^{μ^{'}} (i, j) \geq 4 Θ τ + 16 log n + 22 log 2 - 2 log β$ follows by the choice of $μ^{'}$ .

Next, consider any $ℓ \in [n] ∖ {i, j}$ . From the triangle inequality Lemma 2.20 b it follows that $κ_{i j}^{δ^{'}} \leq κ_{i ℓ}^{δ^{'}} \cdot κ_{ℓ j}^{δ^{'}},$ which gives $ϱ^{μ^{'}} (i, ℓ) + ϱ^{μ^{'}} (ℓ, j) \geq ϱ^{μ^{'}} (i, j) .$ From the bound $Θ ϱ^{μ^{'}} (i, j) \geq 4 Θ τ + 16 log n + 22 log 2 - 2 log β$ , we get that

max {Θ ϱ^{μ^{'}} (i, ℓ), Θ ϱ^{μ^{'}} (ℓ, j)} \geq 2 Θ τ + 8 log n + 11 log 2 - log β .

We next show that if $Θ ϱ^{μ^{'}} (i, ℓ) \geq 2 Θ τ + 8 log n + 11 log 2 - log β$ , then $Ψ^{μ^{'}} (i, ℓ) \geq 2 τ$ . The case $Θ ϱ^{μ^{'}} (ℓ, j) \geq 2 Θ τ + 8 log n + 11 log 2 - log β$ follows similarly.

Consider any $0 < ¯ μ < μ^{'}$ with the corresponding central path point $¯ w = (¯ x, ¯ y, ¯ s)$ . The proof is complete by showing $Θ ϱ^{¯ μ} (i, ℓ) \geq Θ ϱ^{μ^{'}} (i, ℓ) - 8 log n - 11 log 2 + log β$ . Recall that for central path elements, we have $κ_{i j}^{δ^{'}} = κ_{i j} x_{i}^{'} / x_{j}^{'}$ , and $κ_{i j}^{¯ δ} = κ_{i j} {¯ x}_{i} / {¯ x}_{j}$ . Therefore

Θ ϱ^{¯ μ} (i, j) = Θ ϱ^{μ^{'}} (i, j) + log {¯ x}_{i} - log x_{i}^{'} - log {¯ x}_{j} + log x_{j}^{'} .

Using Proposition 3.1, Lemma 3.3 and the assumption $x_{i}^{*} \geq β x_{i} / (2^{10} n^{5.5})$ , we have ${¯ x}_{j} \leq n x_{j}^{'}$ and

{¯ x}_{i} \geq \frac{x_{i}^{*}}{n} \geq \frac{β x_{i}}{2^{10} n^{6.5}} \geq \frac{β (1 - β) x_{i}^{'}}{2^{10} n^{7.5}} \geq \frac{β x_{i}^{'}}{2^{11} n^{7.5}} .

Using these bounds, we get

Θ ϱ^{¯ μ} (i, j)

\geq Θ ϱ^{μ^{'}} (i, j) - 8 log n - 11 log 2 + log β,

completing the proof. ∎

It remains to prove Lemma 4.4 and Lemma 4.5, addressing the more difficult case $ξ_{J}^{l l} < 4 γ n$ . It is useful to decompose the variables into two sets. We let

B := {t \in [n] : | R s_{t}^{l l} | < 4 γ n}, and N := {t \in [n] : | R x_{t}^{l l} | < 4 γ n} .

(44)

The assumption $ξ_{J}^{l l} < 4 γ n$ implies that for every layer $J_{k}$ , either $J_{k} \subseteq B$ or $J_{k} \subseteq N$ . The next two lemma describes the relations between $δ$ and $δ^{+}$ .

Lemma 6.1.

Let $w \in N (β)$ for $β \in (0, 1 / 8]$ , and assume $ℓ^{δ} (J) \leq γ$ and $ε^{l l} (w) < 4 γ n$ . For the next iterate $w^{+} = (x^{+}, y^{+}, s^{+}) \in N (2 β)$ , we have

For $i \in B$ ,

$0.5 \cdot \sqrt{\frac{μ^{+}}{μ}} \leq \frac{δ_{i}^{+}}{δ_{i}} \leq 1. 5 \cdot \sqrt{\frac{μ^{+}}{μ}} and δ_{i}^{- 1} s_{i}^{+} \leq \frac{2 μ^{+}}{\sqrt{μ}} .$
For $i \in N$ ,

$0.5 \cdot \sqrt{\frac{μ}{μ^{+}}} \leq \frac{δ_{i}^{+}}{δ_{i}} \leq 1. 5 \cdot \sqrt{\frac{μ}{μ^{+}}} and δ_{i} x_{i}^{+} \leq \frac{2 μ^{+}}{\sqrt{μ}} .$
If $i, j \in B$ or $i, j \in N$ , then

$\frac{1}{3} \leq \frac{κ_{i j}^{δ}}{κ_{i j}^{δ^{+}}} = \frac{δ_{i}^{+} δ_{j}}{δ_{i} δ_{j}^{+}} \leq 3 .$
If $i \in N$ and $j \in B$ , then

$\frac{κ_{i j}^{δ}}{κ_{i j}^{δ^{+}}} = \frac{δ_{i}^{+} δ_{j}}{δ_{i} δ_{j}^{+}} \geq \frac{β}{9 \sqrt{n} ε^{l l} (w)} \geq 4 n^{3.5} .$

Proof.

Part (i). By Lemma 3.11 a, we see that

	$∥ δ_{B} Δ x_{B}^{l l} ∥_{\infty}$	$\leq ∥ δ_{B} Δ x_{B}^{l l} + δ_{B}^{- 1} Δ s_{B}^{l l} + x_{B}^{1 / 2} s_{B}^{1 / 2} ∥_{\infty} + ∥ δ_{B}^{- 1} (Δ s_{B}^{l l} + s_{B}) ∥_{\infty}$
		$= ∥ δ_{B} Δ x_{B}^{l l} + δ_{B}^{- 1} Δ s_{B}^{l l} + x_{B}^{1 / 2} s_{B}^{1 / 2} ∥_{\infty} + \sqrt{μ} ∥ R s_{B}^{l l} ∥_{\infty}$
		$\leq \sqrt{μ} (6 n ℓ^{δ} (J) + 4 n γ) \leq 10 n γ \sqrt{μ} \leq \sqrt{μ} / 64,$

by the assumption on $ℓ^{δ} (J)$ and the definition of $B$ .

By construction of the LLS step, $| x_{i}^{+} - x_{i} | = α^{+} | Δ x^{l l} | \leq | Δ x^{l l} |$ , by recalling that $0 \leq α_{+} \leq 1$ . Using the bound derived above, for $i \in B$ we get

∣ ∣ ∣ ∣ \frac{x_{i}^{+}}{x_{i}} - 1 ∣ ∣ ∣ ∣ \leq ∣ ∣ ∣ ∣ \frac{Δ x_{i}^{l l}}{x_{i}} ∣ ∣ ∣ ∣ = \frac{| δ_{i} Δ x_{i}^{l l} |}{δ_{i} x_{i}} \leq \frac{\sqrt{μ}}{64 δ_{i} x_{i}} \leq \frac{1}{32},

using also Corollary 3.2. We can write

\frac{δ_{i}^{+}}{δ_{i}} = \sqrt{\frac{x_{i}^{+} s_{i}^{+}}{x_{i} s_{i}}} \cdot \frac{x_{i}}{x_{i}^{+}} .

The claimed bounds follow again using Corollary 3.2 with the choice $β \leq 1 / 8$ .

To get the upper bound on $δ_{i}^{- 1} s_{i}^{+}$ , we use

δ_{i}^{- 1} s_{i}^{+} = \frac{δ_{i}^{+}}{δ_{i} δ_{i}^{+}} s_{i}^{+} = \frac{δ_{i}^{+}}{δ_{i}} \cdot \sqrt{x_{i}^{+} s_{i}^{+}} .

We can upper bound the first term by $1.5 \sqrt{μ^{+} / μ}$ as above, and the second term by $5 \sqrt{μ^{+}} / 4$ again from Corollary 3.2.

Part b.

Analogously to a.

Part c.

Immediate from parts a and b.

Part d.

Follows by parts a and b, and by the lower bound on $\sqrt{μ / μ^{+}}$ obtained from Lemma 3.11 d. ∎

Proof of Lemma 4.4.

Without loss of generality, let $ξ_{J}^{l l} = ξ_{J_{q}}^{l l} = ∥ R x_{J_{q}}^{l l} ∥$ ; thus, $J_{q} \subseteq N$ . The case $ξ_{J_{q}}^{l l} = ∥ R s_{J_{q}}^{l l} ∥$ and $J_{q} \subseteq B$ can be treated analogously.

By Lemma 3.11 c, $∥ R s_{J_{q}}^{l l} ∥ \geq \frac{1}{2} - \frac{3}{4} β > \frac{1}{4} + 2 n γ$ , and therefore Lemma 4.2 provides a $j \in J_{q}$ such that $s_{j}^{*} / s_{j}^{+} \geq 1 / (6 \sqrt{n})$ . Using LABEL:lem:central_path_bounded_l1_norm, $s_{j}^{*} / s_{j} \geq (1 - β) / (6 (1 + 4 β) n^{3 / 2}) > β / (16 n^{3 / 2})$ .

The final statement $ϱ^{μ^{+}} (ℓ, ℓ^{'}) \geq - | J_{q} |$ for any $ℓ, ℓ^{'} \in J_{q}$ is also easy to see. From Lemma 6.1 c and the strong connectivity of $J_{q}$ in $G_{δ, γ / n}$ , we obtain that $J_{q}$ is strongly connected in $G_{δ^{+}, γ / (3 n)}$ . Hence, $ϱ^{μ^{+}} (ℓ, ℓ^{'}) \geq - | J_{q} |$ follows by Lemma 4.1.

The rest of the proof is dedicated to showing the existence of an $i \in J_{q}$ such that $x_{i}^{*} \geq β x_{i}^{+} / (16 n)$ . For this purpose, we will prove that

∥ δ_{J_{q}} x_{J_{q}}^{*} ∥ \geq \frac{β μ^{+}}{8 \sqrt{n μ}} .

(45)

By Lemma 6.1 b, we see that

∥ δ_{J_{q}} x_{J_{q}}^{+} ∥ \leq \sqrt{n} ∥ δ_{J_{q}} x_{J_{q}}^{+} ∥_{\infty} \leq \frac{2 \sqrt{n} μ^{+}}{\sqrt{μ}} .

Thus, the lemma follows immediately from (45): for at least one $i \in J_{q}$ , we must have $x_{i}^{*} / x_{i} \geq β / (16 n)$ .

In order to prove (45), we define

z := (δ^{+})^{- 1} L_{J_{> q}}^{δ^{+}} (δ_{J_{> q}}^{+} (x_{J_{> q}}^{*} - x_{J_{> q}}^{+})) and w := x^{*} - x^{+} - z,

as in Lemma 5.1. By construction, $w \in W$ and $w_{J_{> q}} = 0$ . Thus, $w_{J_{q}} \in W_{J, q}$ .

Using the triangle inequality, we get

∥ δ_{J_{q}} x_{J_{q}}^{*} ∥ \geq ∥ δ_{J_{q}} (x_{J_{q}}^{+} + w_{J_{q}}) ∥ - ∥ δ_{J_{q}} z_{J_{q}} ∥ .

(46)

We bound the two terms separately, starting with an upper bound on $∥ δ_{J_{q}} z_{J_{q}} ∥$ . Since $ℓ^{δ^{+}} (J) \leq 3 γ n$ , we have that

where the last inequality follows by LABEL:lem:central_path_bounded_l1_norm, Corollary 3.2. and $∥ δ^{+} x^{*} ∥ \leq ∥ δ^{+} x^{+} ∥ \cdot ∥ x^{*} / x^{+} ∥_{\infty} \leq \frac{4}{3} n^{3 / 2} \sqrt{μ^{+}}$ . We can use this and Lemma 6.1 b to obtain

∥ δ_{J_{q}} z_{J_{q}} ∥ \leq ∥ δ_{J_{q}} / δ_{J_{q}}^{+} ∥_{\infty} \cdot ∥ δ_{J_{q}}^{+} z_{J_{q}} ∥ \leq \frac{16 n^{2} γ μ^{+}}{\sqrt{μ}} \leq \frac{β μ^{+}}{64 n^{3} \sqrt{μ}},

(47)

using the definition of $γ$ .

The first term in (46) will be bounded as follows.

Claim 6.2.

$∥ δ_{J_{q}} (x_{J_{q}}^{+} + w_{J_{q}}) ∥ \geq \sqrt{μ} ξ_{J}^{l l} / 2$ .

Before proving the claim, we show how the inequality (45), and thus, the lemma, follow. Using Lemma 3.11 d,

μ^{+} \leq \frac{3 \sqrt{n} ξ_{J}^{l l} μ}{β},

implying $∥ δ_{J_{q}} (x_{J_{q}}^{+} + w_{J_{q}}) ∥ \geq β μ^{+} / (6 \sqrt{n μ})$ . Now (45) follows using (46) and (47).

Proof of creftypecap 6.2.

We recall the characterization (24) of the LLS step $Δ x^{l l} \in W$ . Namely, there exists $Δ s \in W_{J, 1}^{⊥} \oplus \dots \oplus W_{J, q}^{⊥}$ that is the unique solution to $δ^{- 1} Δ s + δ Δ x^{l l} = - δ x$ . From the above, note that

∥ δ_{J_{q}}^{- 1} Δ s_{J_{q}} ∥ = ∥ δ_{J_{q}} (x_{J_{q}} + Δ x_{J_{q}}^{l l}) ∥ = \sqrt{μ} ∥ R x_{J_{q}}^{l l} ∥ = \sqrt{μ} ξ_{J}^{l l} .

From the Cauchy-Schwarz inequality,

	$∥ δ_{J_{q}}^{- 1} Δ s_{J_{q}} ∥ \cdot ∥ δ_{J_{q}} (x_{J_{q}}^{+} + w_{J_{q}}) ∥$	$\geq ∣ ∣ ⟨ δ_{J_{q}}^{- 1} Δ s_{J_{q}}, δ_{J_{q}} (x_{J_{q}}^{+} + w_{J_{q}}) ⟩ ∣ ∣$		(48)
		$= ∣ ∣ ⟨ δ_{J_{q}}^{- 1} Δ s_{J_{q}}, δ_{J_{q}} x_{J_{q}}^{+} ⟩ ∣ ∣ .$		(48)

Here, we used that $Δ s_{J_{q}} \in W_{J, q}^{⊥}$ and $w_{J_{q}} \in W_{J, q}$ . Note that

x^{+} = x + α Δ x^{l l} = x + Δ x^{l l} - (1 - α) Δ x^{l l} = - δ^{- 2} Δ s - (1 - α) Δ x^{l l} .

Therefore,

	$∣ ∣ ⟨ δ_{J_{q}}^{- 1} Δ s_{J_{q}}, δ_{J_{q}} x_{J_{q}}^{+} ⟩ ∣ ∣$	$= ∣ ∣ ⟨ δ_{J_{q}}^{- 1} Δ s_{J_{q}}, - δ_{J_{q}}^{- 1} Δ s_{J_{q}} - (1 - α) δ_{J_{q}} Δ x_{J_{q}}^{l l} ⟩ ∣ ∣$
		$\geq ∥ δ_{J_{q}}^{- 1} Δ s_{J_{q}} ∥^{2} - (1 - α) ∣ ∣ ⟨ δ_{J_{q}}^{- 1} Δ s_{J_{q}}, δ_{J_{q}} Δ x_{J_{q}}^{l l} ⟩ ∣ ∣ .$

By Lemma 5.2, there exists $Δ ¯ x \in W_{J, 1} \oplus \dots \oplus W_{J, p}$ such that $∥ δ (Δ x^{l l} - Δ ¯ x) ∥ \leq 2 n ℓ^{δ} (J) \sqrt{μ}$ . Therefore, using the orthogonality of $Δ s_{J_{q}}$ and $Δ {¯ x}_{J_{q}}$ , we get that

∣ ∣ ⟨ δ_{J_{q}}^{- 1} Δ s_{J_{q}}, δ_{J_{q}} Δ x_{J_{q}}^{l l} ⟩ ∣ ∣ = ∣ ∣ ⟨ δ_{J_{q}}^{- 1} Δ s_{J_{q}}, δ_{J_{q}} (Δ x_{J_{q}}^{l l} - Δ {¯ x}_{J_{q}}^{l l}) ⟩ ∣ ∣ \leq 2 n ℓ^{δ} (J) \sqrt{μ} \cdot ∥ δ_{J_{q}}^{- 1} Δ s_{J_{q}} ∥ .

From the above inequalities, we see that

∥ δ_{J_{q}} (x_{J_{q}}^{+} + w_{J_{q}}) ∥ \geq ∥ δ_{J_{q}}^{- 1} Δ s_{J_{q}} ∥ - 2 (1 - α) n ℓ^{δ} (J) \sqrt{μ} = \sqrt{μ} ξ_{J}^{l l} - 2 (1 - α) n ℓ^{δ} (J) \sqrt{μ} .

The claim follows by showing $(1 - α) n ℓ^{δ} (J) \leq ξ_{J}^{l l} / 4$ . From Lemma 3.11 d, we obtain

(1 - α) n ℓ^{δ} (J) \leq 3 n^{3 / 2} ℓ^{δ} (J) ξ_{J}^{l l} / β .

The claim follows by the assumption $ℓ^{δ} (J) \leq γ$ , and the choice of $γ$ . ∎

As pointed out at the beginning of the proof of the claim, this finishes the proof of the lemma. ∎

Proof of Lemma 4.5.

Recall the sets $B$ and $N$ defined in (44). The key is to show the existence of an edge

(i^{'}, j^{'}) \in E_{δ^{+}, γ / (3 n)} such that i^{'} \in J_{q} \subseteq B, j^{'} \in J_{r} \subseteq N, r < q .

(49)

Before proving the existence of such $i^{'}$ and $j^{'}$ , we show how the rest of the statements follow, namely, that $ϱ^{μ^{+}} (i, j) \geq - | J_{q} \cup J_{r} |$ , and for each $ℓ, ℓ^{'} \in J_{q} \cup J_{r}$ , $Ψ^{μ} (ℓ, ℓ^{'}) \leq | J_{q} \cup J_{r} |$ . According to Lemma 4.1, the latter is true (even with the stronger bound $max {| J_{q} |, | J_{r} |}$ ) whenever $ℓ, ℓ^{'} \in J_{q}$ , or $ℓ, ℓ^{'} \in J_{r}$ , or if $ℓ \in J_{q}$ and $ℓ^{'} \in J_{r}$ . It is left to show the lower bound on $ϱ^{μ^{+}} (i, j)$ and $Ψ^{μ} (ℓ, ℓ^{'}) \leq | J_{q} \cup J_{r} |$ for $ℓ^{'} \in J_{q}$ and $ℓ \in J_{r}$ .

From Lemma 6.1 c, we have that if $ℓ, ℓ^{'} \in J_{q} \subseteq B$ or $ℓ, ℓ^{'} \in J_{r} \subseteq N$ , then $κ_{ℓ ℓ^{'}}^{δ} / 3 \leq κ_{ℓ ℓ^{'}}^{δ^{+}}$ . Hence, the strong connectivity of $J_{r}$ and $J_{q}$ in $G_{δ, γ}$ implies the strong connectivity of these sets in $G_{δ^{+}, γ / (3 n)}$ . Together with the edge $(i^{'}, j^{'})$ , we see that every $ℓ^{'} \in J_{q}$ can reach every $ℓ \in J_{r}$ on a directed path of length $\leq | J_{q} \cup J_{r} | - 1$ in $G_{δ^{+}, γ / (3 n)}$ . Applying Lemma 4.1 for this setting, we obtain $Ψ^{μ} (ℓ, ℓ^{'}) \leq ϱ^{μ^{+}} (ℓ, ℓ^{'}) \leq | J_{q} \cup J_{r} |$ for all such pairs, and also $ϱ^{μ^{+}} (i, j) \geq - | J_{q} \cup J_{r} |$ .

The rest of the proof is dedicated to showing the existence of $i^{'}$ and $j^{'}$ as in (49). We let $k \in [p]$ such that $ℓ^{δ^{+}} (J_{\geq k}) = ℓ^{δ^{+}} (J) > 3 n γ$ . To simplify the notation, we let $I = J_{\geq k}$ .

When constructing $J$ In Layering( $δ,^κ$ ), the subroutine Verify-Lift( $W Diag (δ), I, γ$ ) was called for the set $I = J_{\geq k}$ , with the answer ‘pass’. Besides $ℓ^{δ} (I) \leq γ$ , this guaranteed the stronger property that ${max}_{j i} | B_{j i} | \leq γ$ for the matrix $B$ implementing the lift (see Remark 2.12).

Let us recall how this matrix $B$ was obtained. The subroutine starts by finding a minimal $I^{'} \subset I$ such that $dim (π_{I^{'}} (W)) = dim (π_{I} (W))$ . Recall that $π_{I^{'}} (W) ≅ R^{I^{'}}$ and $L_{I}^{δ} (p) = L_{I^{'}}^{δ} (p_{I^{'}})$ for every $p \in π_{I} (W Diag (δ))$ .

Consider the optimal lifting $L_{I}^{δ} : π_{I} (W Diag (δ)) \to W Diag (δ)$ . We defined $B \in R^{([n] ∖ I) \times I^{'}}$ as the matrix sending any $q \in π_{I^{'}} (W Diag (δ))$ to the corresponding vector $[L_{I^{'}}^{δ} (q)]_{[n] ∖ I}$ . The column $B_{i}$ can be computed as $[L_{I^{'}}^{δ} (e^{i})]_{[n] ∖ I}$ for $e^{i} \in R^{I^{'}}$ .

We consider the transformation

This maps $π_{I^{'}} (W Diag (δ^{+})) \to π_{[n] ∖ I} (W Diag (δ^{+}))$ .

Let $z \in π_{I} (W Diag (δ^{+}))$ be the singular vector corresponding to the maximum singular value of $L_{I}^{δ^{+}}$ , namely, $∥ [L_{I}^{δ^{+}} (z)]_{[n] ∖ I} ∥ > 3 n γ ∥ z ∥$ . Let us normalize $z$ such that $∥ z_{I^{'}} ∥ = 1$ . Thus,

∥ ∥ [L_{I^{'}}^{δ^{+}} (z_{I^{'}})]_{[n] ∖ I} ∥ ∥ > 3 n γ .

Let us now apply $¯ B$ to $z_{I^{'}} \in π_{I^{'}} (W Diag (δ^{+}))$ . Since $L_{I}^{δ^{+}}$ is the minimum-norm lift operator, we see that

∥ ∥ ¯ B z_{I^{'}} ∥ ∥ \geq ∥ ∥ [L_{I^{'}}^{δ^{+}} (z_{I^{'}})]_{n ∖ I} ∥ ∥ > 3 n γ .

We can upper bound the operator norm by the Frobenius norm $∥ ¯ B ∥ \leq ∥ ¯ B ∥_{F} = \sqrt{\sum_{j i} {¯ B}_{j i}^{2}} \leq n {max}_{j i} | {¯ B}_{j i} |$ , and therefore

max j i | {¯ B}_{j i} | > 3 γ .

Let us fix $i^{'} \in I^{'}$ and $j^{'} \in [n] ∖ I$ as the indices giving the maximum value of ${¯ B}_{j i}$ . Note that ${¯ B}_{j^{'} i^{'}} = B_{j^{'} i^{'}} δ_{j^{'}}^{+} δ_{i^{'}} / (δ_{i^{'}}^{+} δ_{j^{'}})$ .

Let us now use Lemma 2.10 for the pair $i^{'}, j^{'}$ , the matrix $B$ and the subspace $W Diag (δ)$ . Noting that $B_{j^{'} i^{'}} = [L_{I^{'}}^{δ} (e^{i^{'}})]_{j^{'}}$ , we obtain $κ_{i^{'} j^{'}}^{δ} \geq | B_{j^{'} i^{'}} |$ . Now,

κ_{i^{'} j^{'}}^{δ^{+}} = κ_{i^{'} j^{'}}^{δ} \cdot \frac{δ_{j^{'}}^{+} δ_{i^{'}}}{δ_{i^{'}}^{+} δ_{j^{'}}} \geq | B_{j^{'} i^{'}} | \cdot \frac{δ_{j^{'}}^{+} δ_{i^{'}}}{δ_{i^{'}}^{+} δ_{j^{'}}} = | {¯ B}_{j^{'} i^{'}} | > 3 γ .

(50)

The next claim finishes the proof.

Claim 6.3.

For $i^{'}$ and $j^{'}$ selected as above, (49) holds.

Proof.

$(i^{'}, j^{'}) \in E_{δ^{+}, γ / (3 n)}$ holds by (50). From the above, we have

| B_{j^{'} i^{'}} | > 3 γ \cdot \frac{δ_{i^{'}}^{+} δ_{j^{'}}}{δ_{i^{'}} δ_{j^{'}}^{+}} .

According to Remark 2.12, $| B_{j^{'} i^{'}} | \leq γ$ follows since Verify-Lift( $W Diag (δ), I, γ$ ) returned with ‘pass’. We thus have

\frac{δ_{i^{'}}^{+} δ_{j^{'}}}{δ_{i^{'}} δ_{j^{'}}^{+}} < \frac{1}{3} .

Lemma 6.1 excludes the scenarios $i^{'}, j^{'} \in N$ , $i^{'}, j^{'} \in B$ , and $i^{'} \in N$ , $j^{'} \in B$ , leaving $i^{'} \in B$ and $j^{'} \in N$ as the only possibility. Therefore, $i^{'} \in J_{q} \subseteq B$ and $j^{'} \in J_{r} \subseteq N$ . We have $r < q$ since $i \in I = J_{\geq k}$ and $j \in [n] ∖ I = J_{< k}$ . ∎

∎

7 Initialization

Our main algorithm (Algorithm 2 in Section 3.5), requires an initial solution $w^{0} = (x^{0}, y^{0}, s^{0}) \in N (β)$ . In this section, we remove this assumption by adapting the initialization method of [VY96] to our setting.

We use the “big- $M$ method”, a standard initialization approach for path-following interior point methods that introduces an auxiliary system whose optimal solutions map back to the optimal solutions of the original system. The primal-dual system we consider is

(Init-LP)

The constraint matrix used in this system is

^A = (\begin{matrix} A & 0 & - A I & I & 0 \end{matrix})

The next lemma, asserts that the $¯ χ$ condition number of $^A$ is not much bigger than that of $A$ of the original system (LP).

Lemma 7.1 ([Vy96, Lemma 23]).

${¯ χ}_{^A} \leq 3 \sqrt{2} ({¯ χ}_{A} + 1) .$

We extend this bound for ${¯ χ}^{*}$ .

Lemma 7.2.

${¯ χ}_{^A}^{*} \leq 3 \sqrt{2} ({¯ χ}_{A}^{*} + 1)$ .

Proof.

Let $D \in D_{n}$ and let $^D \in D_{3 n}$ the matrix consisting of three copies of $D$ , i.e.

	$^D$	$= ⎛ ⎜ ⎝ \begin{matrix} D & 0 & 0 0 & D & 0 0 & 0 & D \end{matrix} ⎞ ⎟ ⎠ .$
Then
	$^A^D$	$= (\begin{matrix} A D & - A D & 0 D & 0 & D \end{matrix})$

Row-scaling does not change $¯ χ$ as the kernel of the matrix remains unchanged. Thus, we can rescale the last $n$ rows of $^A^D$ , to the identity matrix, i.e. multiplying by $(I, D^{- 1})$ from the left hand side. So, we observe that

{¯ χ}_{^A^D} = ¯ χ ((\begin{matrix} A D & - A D & 0 I & 0 & I \end{matrix})) \leq 3 \sqrt{2} ({¯ χ}_{A D} + 1)

where the inequality follows from Lemma 7.1. The lemma now readily follows as

{¯ χ}_{^A}^{*}

=inf{¯χ^A^D:D∈D3n}≤inf{3√2(¯χAD+1):D∈Dn}=3√2(¯χ∗A+1).\qed

Also, for sufficiently large $M$ , the optimal solutions of the original system are preserved. We let $d$ be the min-norm solution to $A x = b$ , i.e., $d = A^{⊤} (A A^{⊤})^{- 1} b$ .

Proposition 7.3.

Assume both primal and dual of (LP) are feasible, and $M > max {({¯ χ}_{A} + 1) ∥ c ∥, {¯ χ}_{A} ∥ d ∥}$ . Every optimal solution $(x, y, s)$ to (LP), can be extended to an optimal solution $(x,\lx@converttounder¯x,¯x,y,s,\lx@converttounder¯s,¯s)$ to (Init-LP); and conversely, from every optimal solution $(x,\lx@converttounder¯x,¯x,y,z,s,\lx@converttounder¯s,¯s)$ to (Init-LP), we obtain an optimal solution $(x, y, s)$ by deleting the auxiliary variables.

Proof.

If system (LP) is feasible, it admits a basic optimal solution $(x^{*}, y^{*}, s^{*})$ with basis $B$ such that $A_{B} x_{B}^{*} = b, x^{*} \geq 0, A_{B}^{⊤} y^{*} = c$ and $A^{⊤} y \leq c .$ Using Proposition 2.1 b we see that

	$∥ x_{B}^{*} ∥$	$= ∥ A_{B}^{- 1} b ∥ = ∥ A_{B}^{- 1} A d ∥ \leq {¯ χ}_{A} ∥ d ∥ < M$	(51)
and using that $∥ A ∥ = ∥ A^{⊤} ∥$ we observe
	$∥ A^{⊤} y^{*} ∥$	$= ∥ A^{⊤} A_{B}^{- ⊤} c ∥ \leq ∥ A^{⊤} A_{B}^{- ⊤} ∥ ∥ c ∥ = ∥ A_{B}^{- 1} A ∥ ∥ c ∥ \leq {¯ χ}_{A} ∥ c ∥ < M .$	(52)

We can extend this solution to a solution of system (Init-LP) via setting $¯x∗=2Me−x∗,\lx@converttounder¯x∗=0,z∗=¯s∗=0$ and $\lx@converttounder¯s∗=Me+A⊤y∗$ . Observe that ${¯ x}^{*} > 0$ and $\lx@converttounder¯s∗>0$ by (51) and (52). Furthermore observe that by complementary slackness this extended solution for (Init-LP) is an optimal solution. The property that $\lx@converttounder¯s∗>0$ immediately tells us that $\lx@converttounder¯x$ vanishes for all optimal solutions of (Init-LP) and thus all optimal solutions of (LP) coincide with the optimal solutions of (Init-LP), with the auxiliary variables removed. ∎

The next lemma is from [MT03, Lemma 4.4]. Recall that $w = (x, y, s) \in N (β)$ if $∥ x s / μ (w) - e ∥ \leq β$ .

Lemma 7.4.

Let $w = (x, y, s) \in P^{+ +} \times D^{+ +}$ , and let $ν > 0$ . Assume that $∥ x s / ν - e ∥ \leq τ$ . Then $(1 - τ / \sqrt{n}) ν \leq μ (w) \leq (1 + τ / \sqrt{n}) ν$ and $w \in N (τ / (1 - τ))$ .

The new system has the advantage that we can easily initialize the system with a feasible solution in close proximity to central path:

Proposition 7.5.

We can initialize system (Init-LP) close to the central path with initial solution $w^{0} = (x^{0}, y^{0}, s^{0}) \in N (1 / 8)$ and parameter $μ (w^{0}) \approx M^{2}$ if $M > 15 max {({¯ χ}_{A} + 1) ∥ c ∥, {¯ χ}_{A} ∥ d ∥}$ .

Proof.

The initialization follows along the lines of [VY96, Section 10]. We let $d$ as above, and set

	${¯ x}^{0}$	$=Me,x0=Me,\lx@converttounder¯x0=Me−d$
	$y^{0}$	$= 0, z^{0} = - M e$
	${¯ s}^{0}$	$=Me,s0=Me+c,\lx@converttounder¯s0=Me.$

This is a feasible primal-dual solution to system (Init-LP) with parameter

	$μ^{0}$	$= \frac{3 n M^{2} + M c^{⊤} e - M d^{⊤} e}{3 n} \approx M^{2} .$
We see that
	$∥∥∥¯x0¯s0+x0s0+\lx@converttounder¯x0\lx@converttounder¯s0M2−e∥∥∥2$	$= M^{- 2} ∥ c ∥^{2} + M^{- 2} ∥ d ∥^{2} \leq \frac{1}{9^{2} {¯ χ}_{A}^{2}} \leq \frac{1}{9^{2}} .$

With Lemma 7.4 we conclude that . ∎

Detecting infeasibility

For using the extended system (Init-LP), we still need to assume that both the primal and dual programs in (LP) are feasible. For arbitrary instances, we first need to check if this is the case, or conclude that the primal or the dual (or both) are infeasible.

This can be done by employing a two-phase method. The first phase decides feasibility by running (Init-LP) with data $(A, b, 0)$ and $M > {¯ χ}_{A} ∥ d ∥$ . The objective value of the optimal primal-dual pair is 0 if and only if (LP) has a feasible solution. If the optimal primal/dual solution $(x∗,\lx@converttounder¯x∗,¯x∗,y∗,s∗,\lx@converttounder¯s∗,¯s∗)$ has positive objective value, we can extract an infeasibility certificate in the following way.

By the characterization of ${¯ χ}_{A}$ as in Proposition 2.1 b, there exists an optimal solution $x^{'}$ with ${¯ x}^{'} > 0$ , and so by strong duality, ${¯ s}^{*} = 0$ . From the dual, we conclude that $z = 0$ , and therefore $A^{⊤} y^{*} \leq A^{⊤} y^{*} + s^{*} + z = c = 0$ . On the other hand, by assumption the objective value of the dual is positive, and so $y^{⊤} b \geq y^{⊤} b + 2 M e^{⊤} z > 0$ .

Feasibility of the dual of (LP) can be decided by running (Init-LP) on data $(A, 0, c)$ and $M > ({¯ χ}_{A} + 1) ∥ c ∥$ with the same argumentation: Either the objective of the dual is 0 and therefore the dual optimal solution $(y∗,\lx@converttounder¯s∗,s∗,¯s∗)$ corresponds to a feasible dual solution of (LP) or the objective value is negative and we extract a dual infeasibility certificate in the following way: By assumption $c⊤x≤c⊤x+Me⊤\lx@converttounder¯x<0$ . Furthermore, there exists a basic optimal solution to the dual of (Init-LP) with $\lx@converttounder¯s>0$ and therefore $\lx@converttounder¯x∗=0$ for the optimal primal solution $(\lx@converttounder¯x∗,x∗,¯x∗)$ . So, we have $A x^{*} = b = 0$ , together with $c^{⊤} x < 0$ yielding the certificate.

Finding the right value of $M$

Whereas Algorithm 2 does not require any estimate on ${¯ χ}^{*}$ or $¯ χ$ , for the initialization we need to set $M \geq max {({¯ χ}_{A} + 1) ∥ c ∥, {¯ χ}_{A} ∥ d ∥}$ as in Proposition 7.3.

A straightforward guessing approach (attributed to J. Renegar in [VY96]) starts with a constant guess, say ${¯ χ}_{A} = 100$ , constructs the extended system, and runs the algorithm. In case the optimal solution to the extended system does not map to an optimal solution of (LP), we restart with ${¯ χ}_{A} = 100^{2}$ and try again; we continue squaring the guess until an optimal solution is found.

This would still require a series of $log log {¯ χ}_{A}$ guesses, and thus, result in a dependence on ${¯ χ}_{A}$ in the running time. However, if we initially rescale our system using the near-optimal rescaling Theorem 2.5, the we can turn the dependence from ${¯ χ}_{A}$ to ${¯ χ}_{A}^{*}$ . The overall iteration complexity remains $O (n^{2.5} log n log ({¯ χ}_{A}^{*} + n))$ , since the running time for the final guess on ${¯ χ}_{A}^{*}$ dominates the total running time of all previous computations due to the repeated squaring.

An alternative approach, that does not rescale the system, is to use Theorem 2.5 to approximate ${¯ χ}_{A}$ . In this case we repeatedly square a guess of ${¯ χ}_{A}^{*}$ instead of ${¯ χ}_{A}$ which takes $O (log log {¯ χ}_{A}^{*})$ iterations until our guess corresponds to a valid upper bound for ${¯ χ}_{A}$ .

Note that either guessing technique can handle bad guesses gracefully. For the first phase, if neither a feasible solution to (LP) is returned nor a Farkas’ certificate can be extracted, we have proof that the guess was too low by the above paragraph. Similarly, in phase two, when feasibility was decided in the affirmative for primal and dual, an optimal solution to (Init-LP) that corresponds to an infeasible solution to (LP) serves as a certificate that another squaring of the guess is necessary.

References

[ABGJ18] Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig. Log-barrier interior point methods are not strongly polynomial. SIAM Journal on Applied Algebra and Geometry, 2(1):140–178, 2018.
[AMO93] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., 1993.
[BE14] Sébastien Bubeck and Ronen Eldan. The entropic barrier: a simple and optimal universal self-concordant barrier. arXiv preprint arXiv:1412.1587, 2014.
[Chu14] Sergei Chubanov. A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions. http://www.optimization-online.org/DB_HTML/2014/12/4710.html, 2014.
[CLS19] Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 938–942, 2019.
[Dik67] II Dikin. Iterative solution of problems of linear and quadratic programming. Doklady Akademii Nauk, 174(4):747–748, 1967.
[DLHL15] Jesús A De Loera, Raymond Hemmecke, and Jon Lee. On augmentation algorithms for linear and integer-linear programming: From edmonds–karp to bland and beyond. SIAM Journal on Optimization, 25(4):2494–2511, 2015.
[DLKS19] Jesús A De Loera, Sean Kafer, and Laura Sanità. Pivot rules for circuit-augmentation algorithms in linear optimization. arXiv preprint arXiv:1909.12863, 2019.
[DS08] Samuel I Daitch and Daniel A Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th annual ACM symposium on Theory of Computing, pages 451–460, 2008.
[Fra11] András Frank. Connections in Combinatorial Optimization. Number 38 in Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, 2011.
[GL97] Clovis C. Gonzaga and Hugo J. Lara. A note on properties of condition numbers. Linear Algebra and its Applications, 261(1):269 – 273, 1997.
[Gof80] Jean-Louis Goffin. The relaxation method for solving systems of linear inequalities. Mathematics of Operations Research, 5(3):388–414, 1980.
[Gon92] Clovis C Gonzaga. Path-following methods for linear programming. SIAM review, 34(2):167–224, 1992.
[HT02] Jackie CK Ho and Levent Tunçel. Reconciliation of various complexity and condition measures for linear programming problems and a generalization of Tardos’ theorem. In Foundations of Computational Mathematics, pages 93–147. World Scientific, 2002.
[Kar84] Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pages 302–311, 1984.
[Kha79] Leonid G Khachiyan. A polynomial algorithm in linear programming. In Doklady Academii Nauk SSSR, volume 244, pages 1093–1096, 1979.
[KM13] Tomonari Kitahara and Shinji Mizuno. A bound for the number of different basic solutions generated by the simplex method. Mathematical Programming, 137(1-2):579–586, 2013.
[KOT13] Satoshi Kakihara, Atsumi Ohara Ohara, and Takashi Tsuchiya. Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs. Journal of Optimization Theory and Applications, 157:749–780, 2013.
[KOT14] Satoshi Kakihara, Atsumi Ohara Ohara, and Takashi Tsuchiya. Curvature integrals and iteration complexities in SDP and symmetric cone programs. Computational Optimization and Applications, 57:623–665, 2014.
[KT13] Tomonari Kitahara and Takashi Tsuchiya. A simple variant of the Mizuno–Todd–Ye predictor-corrector algorithm and its objective-function-free complexity. SIAM Journal on Optimization, 23(3):1890–1903, 2013.
[LMT09] Guanghui Lan, Renato DC Monteiro, and Takashi Tsuchiya. A polynomial predictor-corrector trust-region algorithm for linear programming. SIAM Journal on Optimization, 19(4):1918–1946, 2009.
[LS14] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in $~ O (\sqrt{rank})$ iterations and faster algorithms for maximum flow. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 424–433, 2014.
[LS15] Yin Tat Lee and Aaron Sidford. Efficient inverse maintenance and faster algorithms for linear programming. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 230–249, 2015.
[LS19] Yin Tat Lee and Aaron Sidford. Solving linear programs with $~ O (\sqrt{r a n k})$ linear system solves. arXiv preprint 1910.08033, 2019.
[Mad13] Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In Proceedings of the 54th IEEE Annual Symposium on Foundations of Computer Science, pages 253–262. IEEE, 2013.
[Meg83] Nimrod Megiddo. Towards a genuinely polynomial algorithm for linear programming. SIAM Journal on Computing, 12(2):347–353, 1983.
[Meh92] Sanjay Mehrotra. On the implementation of a primal-dual interior point method. SIAM Journal on Optimization, 2(4):575–601, 1992.
[MMT98] Nimrod Megiddo, Shinji Mizuno, and Takashi Tsuchiya. A modified layered-step interior-point algorithm for linear programming. Mathematical Programming, 82(3):339–355, 1998.
[MT03] Renato D. C. Monteiro and Takashi Tsuchiya. A variant of the Vavasis-Ye layered-step interior-point algorithm for linear programming. SIAM Journal on Optimization, 13(4):1054–1079, 2003.
[MT05] Renato D. C. Monteiro and Takashi Tsuchiya. A new iteration-complexity bound for the MTY predictor-corrector algorithm. SIAM Journal on Optimization, 15(2):319–347, 2005.
[MT08] Renato D.C. Monteiro and Takashi Tsuchiya. A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms. Mathematical Programming, 115(1):105–149, 2008.
[MTY93] Shinji Mizuno, Michael Todd, and Yinyu Ye. On adaptive-step primal-dual interior-point algorithms for linear programming. Mathematics of Operations Research - MOR, 18:964–981, 11 1993.
[O’L90] Dianne P. O’Leary. On bounds for scaled projections and pseudoinverses. Linear Algebra and its Applications, 132:115–117, April 1990.
[OV17] Neil Olver and László A. Végh. A simpler and faster strongly polynomial algorithm for generalized flow maximization. In Proceedings of the Forty-Ninth Annual ACM Symposium on Theory of Computing (STOC), pages 100–111, 2017.
[Ren88] James Renegar. A polynomial-time algorithm, based on Newton’s method, for linear programming. Mathematical Programming, 40(1-3):59–93, 1988.
[Ren94] James Renegar. Is it possible to know a problem instance is ill-posed?: some foundations for a general theory of condition numbers. Journal of Complexity, 10(1):1–56, 1994.
[Ren95] James Renegar. Incorporating condition measures into the complexity theory of linear programming. SIAM Journal on Optimization, 5(3):506–524, 1995.
[Sch03] Alexander Schrijver. Combinatorial Optimization – Polyhedra and Efficiency. Springer, 2003.
[SSZ91] György Sonnevend, Josef Stoer, and Gongyun Zhao. On the complexity of following the central path of linear programs by linear extrapolation II. Mathematical Programming, 52(1-3):527–553, 1991.
[ST04] Daniel A Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), 2004.
[Ste89] G.W. Stewart. On scaled projections and pseudoinverses. Linear Algebra and its Applications, 112:189 – 193, 1989.
[Tar85] Éva Tardos. A strongly polynomial minimum cost circulation algorithm. Combinatorica, 5(3):247–255, Sep 1985.
[Tar86] Éva Tardos. A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research, pages 250–256, 1986.
[Tod90] Michael J. Todd. A Dantzig–Wolfe-like variant of Karmarkar’s interior-point linear programming algorithm. Operations Research, 38(6):1006–1018, 1990.
[TTY01] Michael J. Todd, Levent Tunçel, and Yinyu Ye. Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems. Mathematical Programming, 90(1):59–69, Mar 2001.
[Tun99] Levent Tunçel. Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard. Mathematical Programming, 86(1):219–223, Sep 1999.
[Vai89] Pravin M Vaidya. Speeding-up linear programming using fast matrix multiplication. In Proceedings of the 30th IEEE Annual Symposium on Foundations of Computer Science, pages 332–337, 1989.
[Vav94] Stephen A Vavasis. Stable numerical algorithms for equilibrium systems. SIAM Journal on Matrix Analysis and Applications, 15(4):1108–1131, 1994.
[vdB20] Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the Symposium on Discrete Algorithms (SODA), 2020. To appear. Available at https://arxiv.org/abs/1910.11957.
[Vég17] László A. Végh. A strongly polynomial algorithm for generalized flow maximization. Mathematics of Operations Research, 42(2):179–211, 2017.
[VW12] Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the 44th annual ACM symposium on Theory of computing, pages 887–898, 2012.
[VY96] Stephen A. Vavasis and Yinyu Ye. A primal-dual interior point method whose running time depends only on the constraint matrix. Mathematical Programming, 74(1):79–120, 1996.
[Ye97] Yinyu Ye. Interior-Point Algorithms: Theory and Analysis. John Wiley and Sons, New York, 1997.
[Ye05] Yinyu Ye. A new complexity result on solving the Markov decision problem. Mathematics of Operations Research, 30(3):733–749, 2005.
[Ye06] Yinyu Ye. Improved complexity results on solving real-number linear feasibility problems. Mathematical Programming, 106(2):339–363, April 2006.
[Ye11] Yinyu Ye. The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Mathematics of Operations Research, 36(4):593–603, 2011.

	$∥ δ_{J_{k}} Δ x_{J_{k}}^{l l} + δ_{J_{k}}^{- 1} Δ s_{J_{k}}^{l l} + x_{J_{k}}^{1 / 2} s_{J_{k}}^{1 / 2} ∥$	$\leq 6 n ℓ^{δ} (J) \sqrt{μ}, \forall k \in [p], and$		(27)
	$∥ δ Δ x^{l l} + δ^{- 1} Δ s^{l l} + x^{1 / 2} s^{1 / 2} ∥$	$\leq 6 n^{3 / 2} ℓ^{δ} (J) \sqrt{μ} .$		(28)

	$μ (w + α Δ w^{l l})$	$= (1 - α) μ, and$
	$α$	$\geq 1 - \frac{3 \sqrt{n} ε^{l l} (w)}{β} .$

A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix††thanks: Supported by the ERC Starting Grants ScaleOpt and QIP.

Abstract

1 Introduction

Parametrizing by the constraint matrix

Path-following methods and the Vavasis-Ye algorithm

Crossover events and layered least squares steps

Computing good layerings and the ¯χA condition measure

The question of scale invariance and ¯χ∗A

Our contributions.

1.1 Related work

1.2 Organization

2 Finding an approximately optimal rescaling

Notation

Subspace formulation

The condition number ¯χ

Proposition 2.1.

Proof.

Definition 2.2.

Lemma 2.3.

Proof.

Proposition 2.4.

The condition number ¯χ∗A

Theorem 2.5.

2.1 The circuit imbalance measure

Definition 2.6.

Definition 2.7.

Lemma 2.8.

Proof.

Theorem 2.9.

Proof.

Lemma 2.10.

Proof.

Lemma 2.11.

Proof.

Remark 2.12.

2.2 A min-max theorem on κ∗W

Theorem 2.13.

Proof.

Example 2.14.

Corollary 2.15.

Proof.

2.3 Finding circuits: a detour in matroid theory

Proposition 2.16.

Proof.

Lemma 2.17.

Lemma 2.18.

Proof of Lemma 2.18.

Theorem 2.19.

Proof.

The triangle inequality

Lemma 2.20.

Proof.

2.4 Approximating ¯χ and ¯χ∗

Proof of Theorem 2.5.

3 A scaling-invariant layered least squares interior-point algorithm

3.1 Preliminaries on interior-point methods

Proposition 3.1.

Corollary 3.2.

Lemma 3.3.

Proof.

3.2 Predictor and corrector steps

Proposition 3.4.

Minimum norm viewpoint and residuals

Lemma 3.5.

Proof.

Lemma 3.6.

Proof.

3.3 Layered-least-squares direction

3.3.1 A linear system viewpoint

Lemma 3.7.

Proof of Lemma 3.7.

Proposition 3.8.

Proof.

Claim 3.9.

Proof.

3.3.2 Partition lifting scores

Lemma 3.10.

Proof.

Lemma 3.11.

3.4 The layering procedure

A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix^†^†thanks: Supported by the ERC Starting Grants ScaleOpt and QIP.

Computing good layerings and the ${¯ χ}_{A}$ condition measure

The question of scale invariance and ${¯ χ}_{A}^{*}$

The condition number $¯ χ$

The condition number ${¯ χ}_{A}^{*}$

2.2 A min-max theorem on $κ_{W}^{*}$

2.4 Approximating $¯ χ$ and ${¯ χ}^{*}$

Case I: $ξ_{J}^{l l} (w) \geq 4 γ n$ .

Case II: $ξ_{J}^{l l} (w) \leq 4 γ n$ and $ℓ^{δ^{+}} (J) \leq 3 γ n$ .

Case III: $ξ_{J}^{l l} (w) \leq 4 γ n$ and $ℓ^{δ^{+}} (J) > 3 γ n$ .

Finding the right value of $M$